[LeetCode] 199. Binary Tree Right Side View

Posted on | In

Problem

Given 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.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

Explanation 1

  1. In each level, we want to get the most right node. So we can use level-order traversal to solve this problem.

Solution 1

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
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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()) {
            for (int i = queue.size()-1; i >= 0; i--) {
                TreeNode pNode = queue.poll();
                if (i == 0) {
                    res.add(pNode.val);
                }
                if (pNode.left != null) queue.offer(pNode.left);
                if (pNode.right != null) queue.offer(pNode.right);
            }
        }

        return res;
    }
}

Explanation 2

  1. We can also use recursion to solve this problem. First, we create a result list. Pass the result list, the tree root, and the level (depth) which initialize to 0 to the helper function.

  2. In the helper function, the basecase is if the tree node is empty, we immediately return. If the size of the result list is equal to the depth, then we add the tree node value to the result list. Then we recursively call the helper function with the tree node’s right child first, then recursively call the helper function with the tree node’s left child.

Solution 2

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    void helper(TreeNode root, List<Integer> res, int level) {
        if (root == null) return;
        if (res.size() == level) {
            res.add(root.val);
        }
        helper(root.right, res, level+1);
        helper(root.left, res, level+1);
    }

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