1、問題

給定一個(gè)二叉樹，假設(shè)從該二叉樹的右側(cè)觀察它，將觀察到的節(jié)點(diǎn)按照從 上到下的順序輸出。

2、思考與分析

從二叉樹的右側(cè)觀察它，將觀察到的節(jié)點(diǎn)按照從上到下的順序輸出，就是求層次遍歷二叉樹，每層中的最后一個(gè)節(jié)點(diǎn)。

3、算法思路

層次遍歷時(shí)，將節(jié)點(diǎn)與層數(shù)綁定為pair，壓入隊(duì)列時(shí)，將節(jié)點(diǎn)與層數(shù)同時(shí)壓入到隊(duì)列中，并記錄每一層中出現(xiàn)的最后一個(gè)節(jié)點(diǎn)。

在層次遍歷中，每一層中的最后一個(gè)節(jié)點(diǎn)最后遍歷到，隨時(shí)更新對(duì)每層的最后一個(gè)節(jié)點(diǎn)即可。

4、代碼

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

using namespace std;

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

class Solution
{
public:
    vector<int> rightSideView( TreeNode* root )
    {
        vector<int> view; // view[i] 表示第i層的最后一個(gè)節(jié)點(diǎn)，i從0開始
        if ( !root )
            return view;

        // 隊(duì)列中的元素是 <節(jié)點(diǎn)， 層數(shù)>
        queue< pair< TreeNode*, int > > Q;

        if ( root )
            Q.push( make_pair(root, 0) );

        while ( !Q.empty() )
        {
            // 記錄一下首元素，然后將其彈出
            TreeNode* node = Q.front().first;
            int depth = Q.front().second;
            Q.pop();

            // 對(duì)view的更新，有兩種情況
            // 1）view[i] 還沒有，直接push即可
            // 2）view[i] 已經(jīng)存在，但不是最右邊的值，需要將其替換
            if ( view.size() == depth)
                view.push_back( node->val );
            else
            {
                // view.pop_back();
                // view.push_back( node->val );
                view[view.size() - 1] = node->val;
            }

            if ( node->left )
                Q.push( make_pair( node->left, depth + 1));
            if ( node->right )
                Q.push( make_pair( node->right, depth + 1));
        }
        return view;
    }
};

int main()
{
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    TreeNode d(5);
    TreeNode e(4);
    TreeNode f(6);

    a.left = &b;
    a.right = &c;
    b.right = &d;
    c.right = &e;
    d.left = &f;

    vector<int> view;
    Solution S;
    view = S.rightSideView(&a);

    for (int i = 0; i < view.size(); i++)
    {
        cout << view[i] << endl;
    }

    return 0;
}