199.二叉树的右视图.md

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

eg:

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

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

思路描述：直观思路就是层次遍历整棵二叉树，然后取出每一层最右边的val。层次遍历的实现可以用BFS来完成，对每一层从左到右访问。广搜过程大家都很熟悉了，因为我们还是需要知道每一层的最后一个val，如果是满二叉树的话，就比较容易了，因为每一层结点的个数是 $2^n$，第一层n=0，那么第k层最后一个结点的序号是

$1+2+2^2+...+2^{k-1}=2^k-1$

所以我们要给每个结点编序号，但是遇到null结点的话就不好办了，所以我们想想可不可以给每个结点编上层号，如果编上层号的话，那么相同层号的最后一个就是我们要找的节点了，这时候我们可以使用hash表去存节点和层号之间的关系。

然后我们用floor存层号，lastVal存上一个值。如果检测到层号刚好增长，那么lastVal就是上一层最后一个值，为什么这样做而不是直接去遍历hash表呢，因为你存进去的顺序和输出的顺序是不一致的。

/**
 * 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) {
        if(root == NULL) return {};
        queue<TreeNode*> Q;
        vector<int> ans;
        Q.push(root);
        unordered_map<TreeNode*, int> nodes;
        nodes.insert(make_pair(root,0));
        //上一层是第0层，最后一个值是root的值
        int floor = 0, lastVal = root->val;
        while(!Q.empty()){
            TreeNode* node = Q.front();
            Q.pop();
            // cout << node->val;
            //左右子节点的层数是父节点的层数加1
            if(node->left != NULL) {
                Q.push(node->left);
                nodes[node->left] = nodes[node] + 1;
                //如果层号恰好比上一次记录的层号要大，那么就更新层号
                //并记录值
                if(nodes[node->left] > floor){
                    floor = nodes[node->left];
                    ans.push_back(lastVal);
                }
                lastVal = node->left->val;
            }
            if(node->right != NULL){
                Q.push(node->right);
                nodes[node->right] = nodes[node] + 1;
                 if(nodes[node->right] > floor){
                    floor = nodes[node->right];
                    ans.push_back(lastVal);
                }
                lastVal = node->right->val;
            } 
        }
        ans.push_back(lastVal);
        return ans;       
    }
};

但是空间消耗有点多，其实unordered_map我们也没太用到，所以我们可以进行如下优化，我们用两个指针last和nlast分别代表上一层的最后一个节点和下一层的最后一个节点。我这里口头描述一下。

   1           
 /   \
2     3         
 \     \
  5     4  

刚开始last和nlast都指向root，然后nlast更新为root的右节点，因为root=last，那么把root->val存入ans，然后把last更新为nlast，为什么last一定是上一层的最后一个节点呢？因为push进队列的刚开始是root，然后是root的左右结点，然后是root的左右结点的左右结点...，而更新last的条件是要满足当前位与队列头部的结点等于last，也就是上一次的右节点。我感觉说的不是很清楚，我也不太会做动图，看代码可以看出来last一直是向右靠拢的。

/**
 * 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) {
        if(root == NULL) return {};
        queue<TreeNode*> Q;
        vector<int> ans;
        Q.push(root);
      	TreeNode* last = root, *nlast = root;
        int floor = 0, lastVal = root->val;
        while(!Q.empty()){
            TreeNode* node = Q.front();
            Q.pop();
            if(node->left){
            	nlast = node->left;
                Q.push(node->left);
            }
            if(node->right){
                nlast = node->right;
                Q.push(node->right);
            }
            if(node == last){
                ans.push_back(node->val);
                last = nlast;
            }
        }
        return ans;       
    }
};