Problem description:

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:

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

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

Solution:

  • DFS solution:
  1. observe the tree, we can see that if we use a recursive traversal with a depth variable, we can get the rightmost element for each level.
  2. traverse the right subtree first, then search for left subtree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        self.res = []
        level = 1
        def dfs(root, level):
            # we only keep the rightest node in result, means every level only one node
            if not root:
                return
            if level > len(self.res):
                self.res.append(root.val)
            dfs(root.right, level+1)
            dfs(root.left, level+1)
        dfs(root, 1)
        return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//DFS solution
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        helper(res, root, 0);
        return res;
    }
    
    void helper(vector<int>& res, TreeNode* cur, int depth){
        if(!cur) return;
        
        if(depth == res.size()){
            res.push_back(cur->val);
        }
        
        helper(res, cur->right, depth+1);
        helper(res, cur->left, depth+1); //if a root have right and left node, the right node will add to res already, so left will not be pushed into res.
    }
};

time complexity: O(n)
space complexity: O(n)

  • BFS solution:
  1. for BFS, we traverse each level with a queue.
  2. push the newest element in queue to res. That is because the way we traverse, will look like this.
    1
    2
    3
         1
      2    3 
    4  5  6  7

queue: 7 6 5 4, 4 will be pushed into queue first, 7 will be the last and right most element.

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.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;
        if(!root) return res;
        
        q.push(root);
        while(!q.empty()){
            res.push_back(q.back()->val);
            for(auto i= q.size(); i>0; i--){
                auto front= q.front();
                q.pop();
                if(front->left) q.push(front->left);
                if(front->right) q.push(front->right);
            }
        }
        return res;
    }
};
  • BFS python
    Use deque to store node in each level, then append child nodes in new deque.
    The idea is to push the right most node last, so it would make sure stack[-1] is the rightest one.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        deque = collections.deque()
        if root:
            deque.append(root)
        res = []
        while deque:
            newStack = collections.deque()
            res.append(deque[-1].val)
            for _ in range(len(deque)):
                node = deque.popleft()
                if node.left:
                    newStack.append(node.left)
                if node.right:
                    newStack.append(node.right)
            deque = newStack
        return res

reference:
https://goo.gl/sWGD8V
https://goo.gl/ZefCkV