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.

For example:

Given the following binary tree,

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

 

You should return [1, 3, 4]. 

 

这是一道medium的题，但是刚开始感觉不难。首先看到这道题的第一反应就是层序遍历，用队列。以前考研的时候看到过层序遍历，不过真心不记得了。后来自己想偏了，又说想用栈。

这道题就是把每一层的节点从左到右的入队（此时就可以计算一下队的大小，这个我一直没有想到，这样就可以计算出每一层有多少个节点了。），然后取最后一个节点的值入结果vector。假设我们第一层扫描完了（即它的孩子已经入队了），每扫描完了以后就会删掉你扫描的节点，那么当你把第一层的节点扫描完，第二层节点已经入队且第一层的节点已经被删除掉了，此时队列里只有第二层的节点，然后我们取最后一个的值入结果vector，就是最右的（因为我们是从左到右入队的）。同理，扫描第二层节点，扫描完了以后第二层节点已经全部被删除，队列里只有第三层节点。直至队列里没有节点了，说明新的一层一个节点没有，那就是树到底了。附代码。（这道题自己没做出来，后来参考别人的。。）

 

using namespace std;/** * 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
     
       rightSideView(TreeNode* root) {        int val=0,sizequeue=0;        vector
      
        result;        if(root==NULL) return result;        queue
       
         TreeQueue;        TreeQueue.push(*root);        while(!TreeQueue.empty()){                        val=(TreeQueue.back()).val;            result.push_back(val);            sizequeue=TreeQueue.size();            for(int i=0;i
        
         left!=NULL)  TreeQueue.push(*(root->left));                if(root->right!=NULL) TreeQueue.push(*(root->right));                }            }    return result;}};