LeetCode/solutions/199. Binary Tree Right Side View.md

# [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)

# 思路
此题属于二叉树层序遍历的应用，关于[二叉树层序遍历之前分析](https://github.com/ShusenTang/LeetCode/blob/master/solutions/102.%20Binary%20Tree%20Level%20Order%20Traversal.md)过这里就不说了。

# C++
## 写法一
每次循环只访问一个节点，用last指针指向当前层的最后一个节点。
``` C++
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        queue<TreeNode *>q;
        TreeNode *last = root, *p = NULL;
        q.push(root);
        
        while(!q.empty()){
            p = q.front(); q.pop();
            if(p -> left) q.push(p -> left);
            if(p -> right) q.push(p -> right);
            
            if(last == p){
                res.push_back(last -> val);
                last = q.back();
            }
        }
        return res;
    }
};
```

## 写法二
每次循环访问一层节点。
``` C++
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        queue<TreeNode *>q;
        TreeNode *p = NULL;
        q.push(root);
        
        while(!q.empty()){
            res.push_back(q.back() -> val);
            
            for(int i = q.size(); i > 0; i--){
                p = q.front(); q.pop();
                if(p -> left) q.push(p -> left);
                if(p -> right) q.push(p -> right);
            }
        }
        return res;
    }
};
```