199. 二叉树的右视图

难度中等186

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

1
2
3
4
5
6
7
8
9
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

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

通过次数29,576

提交次数46,105

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* 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) {
//bfs
// 1
//2 3
// 5 4
//广度优先搜索,当q里面只有最右边一个元素的时候把这个元素加入到输出的队列里面;
// if(root==nullptr){return NULL};
vector<int>result;
if(root==nullptr){return result;};
queue<TreeNode*>q;//先进先出
q.push(root);
while(!q.empty()){
// TreeNode*temp=q.front();
//关键点: 用len记录q的size;通过这个来获得最右侧的点;
int len=q.size();
for(int i=0;i<len;i++){
TreeNode*temp=q.front();
if(i==len-1){
result.push_back(temp->val);
}
q.pop();
if(temp->left!=nullptr){
q.push(temp->left);
}
if(temp->right!=nullptr){
q.push(temp->right);
}

}
}
return result;


}
};