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;


    }
};