leetcode--199--二叉树的右视图

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

示例:

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

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

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

思路：
1、层次遍历这个二叉树，然后将每一层中最右边的值保存起来即可

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        if not root:
            return ret;
        layer = [root]
        while layer:
            ret.append(layer[-1].val)
            new_layer = []
            for node in layer:
                if node.left:
                    new_layer.append(node.left)
                if node.right:
                    new_layer.append(node.right)
            layer = new_layer
        return ret

C++代码：

/**
 * 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) {
        vector<int> ret;
        if (root == nullptr) return ret;

        vector<TreeNode*> layer;
        layer.push_back(root);
        while(layer.size()>0){
            vector<TreeNode*> new_layer;
            int item = layer[layer.size()-1]->val;
            ret.push_back(item);
            for (auto node:layer){
                if (node->left) new_layer.push_back(node->left);
                if (node->right) new_layer.push_back(node->right);
            }
            new_layer.swap(layer);
        }
        return ret;
    }
};