# [LeetCode] 199. Binary Tree Right Side View 二叉树的右侧视图

2021年09月15日 阅读数：1

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

Example:java

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

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

Python:　DFS　node

```# Time:  O(n)
# Space: O(h)
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution(object):
# @param root, a tree node
# @return a list of integers
def rightSideView(self, root):
result = []
self.rightSideViewDFS(root, 1, result)
return result

def rightSideViewDFS(self, node, depth, result):
if not node:
return

if depth > len(result):
result.append(node.val)

self.rightSideViewDFS(node.right, depth+1, result)
self.rightSideViewDFS(node.left, depth+1, result)
```

Python: BFS　　python

```# Time:  O(n)
# Space: O(n)
class Solution2(object):
# @param root, a tree node
# @return a list of integers
def rightSideView(self, root):
if root is None:
return []

result, current = [], [root]
while current:
next_level = []
for node in current:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
result.append(node.val)
current = next_level

return result
```

Python: 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.app

```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):]
```

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

```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　```

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

```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　　```

C++: DFSthis

```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;
}
};
```

C++:　BFS　url

```class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
res.push_back(q.back()->val);
int size = q.size();
for (int i = 0; i < size; ++i) {
TreeNode *node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}
};
```

[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历 II