[数据结构与算法]算法：二叉树的右视图

leetcode 二叉树的右视图

二叉树一个基本的数据结构，在其使用中可能会牵扯到栈或队列的使用。

给定一个二叉树，只输出其从右侧看到的节点的值，且从上往下遍历。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Node {
    TreeNode node;
    int layer;
    Node(TreeNode node, int layer) {
        this.node = node;
        this.layer = layer;
    }
    public TreeNode getNode() {
        return this.node;
    }
    public int getLayer() {
        return this.layer;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<Node> queue = new LinkedList<Node>();
        List<Integer> result = new ArrayList();
        if (root == null) return result;
        queue.offer(new Node(root, 0));
        while (queue.size() > 0) {
            Node node = queue.poll();
            TreeNode treeNode = node.getNode();
            int layer = node.getLayer();
            if (queue.size() == 0 || queue.peek().getLayer() > layer) {
                result.add(treeNode.val);
            }
            if (treeNode.left != null) queue.offer(new Node(treeNode.left, layer + 1));
            if (treeNode.right != null) queue.offer(new Node(treeNode.right, layer + 1));
        }
        return result;
    }
}

这里使用 Java 进行编写，因为使用栈有现成的类，使用较为方便。

创建了一个新类，存储节点和其处于的层数。按层级遍历这个数，使用一个队列来存储遍历到的节点，当其为队列中最后一个节点或其下一个节点的所处的层数是当前节点的层（层数比当前节点大），此节点就为右视图可以看到的节点。就将其值加入到结果中。对于每一个节点，先把它的左节点加入到队列中，再把它的右节点加入到内存中。

结果：

似乎可以尝试用一个链表来实现一个队列，可以用来尝试解决这个问题，其每个节点应包含，树节点的指针，层数，其当前节点的下一个指针，对于使用双向还是使用双向链表，取决于题目的需要，这里只需要单向链表就可以了，但是要分别记录头节点和尾节点。