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

Credits:

分析：层次遍历，取最右面的元素：

方法一：双q法：

 

class Solution {    public:        vector
     
        rightSideView(TreeNode *root)        {            queue
      
        q1;            queue
       
         q2;            vector
        
           res;            if(root != NULL)            {                q1.push(root);            }            while(!q1.empty())            {                TreeNode * p = q1.front();                q1.pop();                if(p->left)                    q2.push(p->left);                if(p->right)                    q2.push(p->right);                if(q1.empty() /*&& !q2.empty()*/)                {                    res.push_back(p->val);                    swap(q1, q2);                }            }            return res;        }};
        
       
      
     

 

方法二：单q+ NULL标记level结束法

/** * 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) {            vector
      
        rtn;            if(root == NULL)                return rtn;            queue
       
         q;            TreeNode* pre = NULL;            q.push(root);            q.push(NULL);//mark the end of this level            while(!q.empty())            {                   TreeNode * p = q.front();                q.pop();                if(p == NULL)                 {                       rtn.push_back(pre->val);                    if(!q.empty())// some elements still exist in q.                        q.push(NULL);//mark end of this level                }                   else                {                       if(p->left)                        q.push(p->left);                    if(p->right)                        q.push(p->right);                }                   pre = p;            }            return rtn;        }};