199.二叉树的右视图

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

示例 1:

img

1
2
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

1
2
输入: [1,null,3]
输出: [1,3]

示例 3:

1
输入: []

Solution

层序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Deque <TreeNode> deque=new ArrayDeque<>();
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        deque.offer(root);
        while(!deque.isEmpty()){
            List<Integer> ans=new ArrayList<>();
            int size=deque.size();
            for (int i = 0; i < size; i++) {
            TreeNode temp=deque.poll();
                if(temp.right!=null){
                    deque.offer(temp.right);
                }
                if(temp.left!=null){
                    deque.offer(temp.left);
                }
                ans.add(temp.val);
            }
            list.add(ans.get(0));
        }
        return list;
    }
}

递归：

设置一个深度的参数，只记录深度和目前递归深度相同的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private final List<Integer> ans = new ArrayList<>();

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

    private void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (depth == ans.size())
            ans.add(root.val);
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
}