问题

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

示例:
输入：[1,2,3,null,5,null,4]
输出：[1, 3, 4]
解释：

1 <—-
/ \
2 3 <—-
\ \
5 4 <—-

思路

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进res数组中，随后返回res就可以了

解法一：自解

  1. class Solution {
  2.     public List<Integer> rightSideView(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         if(root == null){
  5.             return res;
  6.         }
  8.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  9.         queue.offer(root);
  10.         while(!queue.isEmpty()){
  11.             int size = queue.size();
  12.             for(int i = 0; i < size; i++) {
  13.                 TreeNode node = queue.poll();
  14.                 if(i == (size - 1)){
  15.                     res.add(node.val);
  16.                 }
  17.                 if (node.left != null) {
  18.                     queue.offer(node.left);
  20.                 }
  21.                 if (node.right != null) {
  22.                     queue.offer(node.right);
  23.                 }
  24.             }
  25.         }
  26.         return res;
  27.     }
  28. }

解法二：BFS

利用广度优先搜索进行层次遍历，记录下每层的最后一个元素

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

解法三：DFS

我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。（与先序遍历 「根结点 -> 左子树 -> 右子树」 正好相反，先序遍历每层最先访问的是最左边的节点）

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (depth == res.size()) {   // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}