199. Binary Tree Right Side View

  • 39.5%

https://leetcode.com/problems/binary-tree-right-side-view/#/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.

1
2
3
4
5
6
7
8
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].

方法一:

层序遍历/广度优先搜索

o(N)时间 o(N)空间

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;
if(!root) return res;
queue<TreeNode*> que;
que.push(root);
while(que.size()){
int n = que.size();
for(int i=0; i<n; i++){
TreeNode* cur = que.front();
que.pop();
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
if(i==n-1)
res.push_back(cur->val);
}
}
return res;
}
};

方法二:

递归,从先序遍历改造而来

https://discuss.leetcode.com/topic/11310/my-c-solution-modified-preorder-traversal

My C++ solution, modified preorder traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
void recursion(TreeNode *root, int level, vector<int> &res)
{
if(root==NULL) return ;
if(res.size()<level) res.push_back(root->val);
recursion(root->right, level+1, res);
recursion(root->left, level+1, res);
}

vector<int> rightSideView(TreeNode *root) {
vector<int> res;
recursion(root, 1, res);
return res;
}
};

我的代码实现:

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.
* 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;
helper(root, res, 0);
return res;
}

void helper(TreeNode* root, vector<int>& res, int level){
if(!root)
return;
if(res.size()==level) res.push_back(root->val);
helper(root->right, res, level+1);
helper(root->left, res, level+1);
}
};

https://discuss.leetcode.com/topic/23030/simple-c-solution-btw-i-like-clean-codes

Simple C++ solution (BTW: I like clean codes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void dfs(TreeNode* root, int lv, vector<int> &res){
if(!root) return;
if(lv>=res.size()) res.push_back(root->val);
dfs(root->right,lv+1,res);
dfs(root->left,lv+1,res);
}

vector<int> rightSideView(TreeNode* root) {
vector<int> res;
dfs(root, 0, res);
return res;
}
};

https://discuss.leetcode.com/topic/11303/9ms-c-bfs-o-n-time-concise-with-explanation

9ms C++ BFS, O(n) time, concise with explanation

9ms C++ iterative, concise code with explanation

Using a queue mQ to perform level order traversal. In the beginning of a level traversal, the last element is pushed into result array ret. The core idea is similar with Binary Tree Level Order Traversal

O(n) time, O(logn) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
queue<TreeNode*>mQ;
vector<int> ret;
if(!root)return ret;
mQ.push(root);
while(!mQ.empty()){
ret.push_back(mQ.back()->val);
for(int i=mQ.size();i>0;i--){
TreeNode *tn=mQ.front();
mQ.pop();
if(tn->left)mQ.push(tn->left);
if(tn->right)mQ.push(tn->right);
}
}
return ret;
}
};

https://discuss.leetcode.com/topic/16164/5-9-lines-python-48-ms

5-9 Lines Python, 48+ ms

Solution 1: Recursive, combine right and left: 5 lines, 56 ms

Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.

1
2
3
4
5
6
def rightSideView(self, root):
if not root:
return []
right = self.rightSideView(root.right)
left = self.rightSideView(root.left)
return [root.val] + right + left[len(right):]

Solution 2: Recursive, first come first serve: 9 lines, 48 ms

DFS-traverse the tree right-to-left, add values to the view whenever we first reach a new record depth. This is O(n).

1
2
3
4
5
6
7
8
9
10
def rightSideView(self, root):
def collect(node, depth):
if node:
if depth == len(view):
view.append(node.val)
collect(node.right, depth+1)
collect(node.left, depth+1)
view = []
collect(root, 0)
return view

Solution 3: Iterative, level-by-level: 7 lines, 48 ms

Traverse the tree level by level and add the last value of each level to the view. This is O(n).

1
2
3
4
5
6
7
8
def rightSideView(self, root):
view = []
if root:
level = [root]
while level:
view += level[-1].val,
level = [kid for node in level for kid in (node.left, node.right) if kid]
return view

1ms, 82.64%, July 14th, 2016

https://discuss.leetcode.com/topic/11768/my-simple-accepted-solution-java

My simple accepted solution(JAVA)

The core idea of this algorithm:

  1. Each depth of the tree only select one node.

  2. View depth is current size of result list.

Here is the code:

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

public void rightView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}

rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);

}
}
谢谢你,可爱的朋友。