0199.md

199. Binary Tree Right Side View

Level:

Topic:

Similar Problem:

• 102. Binary Tree Level Order Traversal

Question

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Intuition

Recursive: Instead of traversing left child first, traverse the right child. So every time to the next level traversal, the first node will be guaranteed the rightside node.

Iterative: Same approach in 102, use bfs and queue to store very level's node and the last node must be the rightside node.

Code

Time: O(n)
Space: O(n)

Iterative

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();

    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null)
        queue.add(root);

    while (!queue.isEmpty()) {
        int n = queue.size();
        while (n-- > 0) {
            root = queue.poll();
            if (root.left != null)
                queue.add(root.left);
            if (root.right != null)
                queue.add(root.right);
        }
        ans.add(root.val);
    }

    return ans;
}

Time: O(n)
Space: O(d), diameter of the level

Recursive

List<Integer> rightside = new ArrayList();

public void helper(TreeNode node, int level) {
    if (node == null)
        return;

    if (level == rightside.size())
        rightside.add(node.val);

    helper(node.right, level + 1);
    helper(node.left, level + 1);
}

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