题目描述

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

解析

  这一题的关键其实就是找到怎么去得到当前是哪一层级，可以利用队列对二叉树进行层次遍历，但是需要稍微修改下遍历方式，每次都将该层遍历完。

public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();  // 返回空列表而非null
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelLength = queue.size();  // 当前层的长度
            for (int i = 0; i < levelLength; i++) {
                TreeNode node = queue.poll();
                // 仅在遍历到当前层最后一个元素时记录
                if (i == levelLength - 1) {
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }

  然后深度优先遍历也是可以求解。优先遍历右子树，同时记录下当前遍历到的层级即可。

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    private void dfs(TreeNode node, int depth, List<Integer> ans) {
        if (node == null) {
            return;
        }
        if (ans.size() == depth) {
            ans.add(node.val);
        }
      
        depth++;
        dfs(node.right, depth, ans);
        dfs(node.left, depth, ans);
    }