Leetcode_199_Binary Tree Right Side View

[lihe]

Binary Tree Right Side View

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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

题意：这题就是求二叉树每层的最右边的节点。

算法思路：

1. 层序遍历时，将节点与层数绑定为pair，压入队列中；
2. 将每层的最后一个节点压入到view中。

class Solution{
public:
    std::vector<int> rightSideView(TreeNode* root){
        std::vector<int> view;
        std::queue<std::pair<TreeNode*, int>> Q;
        if(root){
            Q.push(std::make_pair(root, 0));
        }
        while(!Q.empty()){
            TreeNode* node = Q.front().first;
            int depth = Q.front().second;
            Q.pop();
            if(view.size() == depth){
                view.push_back(node -> val);
            }
            else{
                view[depth] = node -> val;
            }
            if(node -> left){
                Q.push(std::make_pair(node -> left, depth + 1));
            }
            if(node -> right){
                Q.push(std::make_pair(node -> right, depth + 1));
            }
        }
        return view;
    }
};