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

For example:
Given the following binary tree,

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

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

題解：

輸入一個(gè)二叉樹，從右側(cè)觀察二叉樹，將觀察到的節(jié)點(diǎn)從上到下的順序輸出；
分析題目，能夠看出，如果我們從右側(cè)觀察二叉樹；那么能夠觀察到的節(jié)點(diǎn)一定是該二叉樹每層的最右邊的節(jié)點(diǎn)；那么，我們只需要對(duì)二叉樹寬度優(yōu)先搜索的時(shí)候，存入節(jié)點(diǎn)及節(jié)點(diǎn)所在的層數(shù)，就不難求出每層最右邊的節(jié)點(diǎn)；
二叉樹的寬度優(yōu)先搜索：http://www.itdecent.cn/p/9a0f3e29b479

層次遍歷的時(shí)候如何將節(jié)點(diǎn)和節(jié)點(diǎn)所在層數(shù)同時(shí)存在隊(duì)列（queue）中呢？
我們想到了STL的另一個(gè)容器：對(duì)組（pair）；
對(duì)組功能：將一對(duì)值合成一個(gè)值，且這對(duì)值可以是任意數(shù)據(jù)類型；
本題我們要用對(duì)組存儲(chǔ)二叉樹節(jié)點(diǎn)和該節(jié)點(diǎn)所在層數(shù)；
所以：pair<TreeNode *, int> p;
兩個(gè)值分別用 pair 的 first 和 second 訪問：
p.first 表示二叉樹節(jié)點(diǎn) root；
p.second : 表示節(jié)點(diǎn)所在層數(shù) level；
初始化一個(gè)pair可以使用構(gòu)造函數(shù)，也可以使用std::make_pair函數(shù)；
std::make_pair(root, level);

好了，在我們能夠把二叉樹節(jié)點(diǎn)和對(duì)應(yīng)的層數(shù)同時(shí)保存以后，我們就可以愉快地對(duì)二叉樹寬度優(yōu)先搜索，然后搜索過程中存入每一層的最后出現(xiàn)的節(jié)點(diǎn)的值啦；
對(duì)二叉樹寬度優(yōu)先搜索需要借助隊(duì)列實(shí)現(xiàn)，隊(duì)列存入每次搜索后得到的二叉樹節(jié)點(diǎn)和節(jié)點(diǎn)層數(shù)；所以要將對(duì)數(shù)放入隊(duì)列中進(jìn)行層次遍歷；
所以最終的聲明為：queue<pair<TreeNode *, int>> q;
定義一個(gè)vector數(shù)組（vector<int> node_val）
用它來存儲(chǔ)每層的最右節(jié)點(diǎn)值 node_val [level] ；
level = q.front().second；
能夠發(fā)現(xiàn)，我們只需要不斷的更新node_val [level] 的值，就可以得到層次遍歷時(shí)，在第 level層中最后搜索到的節(jié)點(diǎn)（最右邊的節(jié)點(diǎn)）；
層次遍歷結(jié)束后得到的 vector 即為從右側(cè)觀察二叉樹觀察到的從上到下順序輸出的節(jié)點(diǎn)；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    //vector<pair<int, int>> rightSideView(TreeNode *root) {
    vector<int> rightSideView(TreeNode *root) {
        queue<pair<TreeNode *, int>> q;
        //vector<pair<int, int>> result;
        vector<int> node_val;
        if (!root) {
            return node_val;
        }
        int level = 0;
        q.push(make_pair(root, level));
        node_val.push_back(root->val);
        while (!q.empty()) {
            if (q.front().first->left) {
                level += 1;
                q.push(make_pair(q.front().first->left, q.front().second + 1));
            }
            if (q.front().first->right) {
                level += 1;
                q.push(make_pair(q.front().first->right, q.front().second + 1));
            }
            if (node_val.size() < q.front().second + 1) {
                node_val.push_back(q.front().first->val);
            }
            if(node_val.size() == q.front().second + 1){
                node_val.pop_back();
                node_val.push_back(q.front().first->val);
            }
            //result.push_back(make_pair(q.front().first->val, q.front().second));
            q.pop();
        }
        return node_val;
        //return result;
    }
};

int main() {
    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode i(5);
    TreeNode j(1);
    a.left = &b;
    b.left = &d;
    d.left = &g;
    d.right = &h;
    a.right = &c;
    c.left = &e;
    c.right = &f;
    f.left = &i;
    f.right = &j;
    Solution s;
    //vector<pair<int, int>> result;
    //result = s.rightSideView(&a);
    vector<int> result;
    result = s.rightSideView(&a);
    for (int i = 0; i < result.size(); i++) {
        printf("%d->", result[i]);
    }
    return 0;
}

結(jié)果

5->8->4->1->

My Solution(Python)

import queue
# 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]
        """
        if not root:
            return []
        Q = queue.Queue()
        level = 0
        val = []
        Q.put([root, level])
        while not Q.empty():
            root, level = Q.get()
            if root.left:
                Q.put([root.left, level + 1])
            if root.right:
                Q.put([root.right, level + 1])
            val.append(root.val)
            val[level] = root.val
        return val[:level + 1]