199. Binary Tree Right Side View

, ,

BFS

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
27
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> numList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (i == 1) { // 注意此处是与 1 比较
                    numList.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return numList;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> numList = new ArrayList<>();
        dfs(numList, root, 0);
        return numList;
    }

    private void dfs(List<Integer> numList, TreeNode node, int depth) {
        if (node == null) {
            return;
        }

        if (numList.size() == depth) {
            numList.add(node.val);
        }
        dfs(numList, node.right, depth + 1);
        dfs(numList, node.left, depth + 1);
    }
}

References

199. Binary Tree Right Side View
剑指 Offer II 046. 二叉树的右侧视图