Leetcode199、二叉树侧视图（从侧面观察二叉树）

1、问题

给定一个二叉树，假设从该二叉树的右侧观察它，将观察到的节点按照从 上到下的顺序输出。

2、思考与分析

从二叉树的右侧观察它，将观察到的节点按照从上到下的顺序输出，就是求层次遍历二叉树，每层中的最后一个节点。

3、算法思路

层次遍历时，将节点与层数绑定为pair，压入队列时，将节点与层数同时压入到队列中，并记录每一层中出现的最后一个节点。

在层次遍历中，每一层中的最后一个节点最后遍历到，随时更新对每层的最后一个节点即可。

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层的最后一个节点，i从0开始
        if ( !root )
            return view;

        // 队列中的元素是 <节点， 层数>
        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();

            // 对view的更新，有两种情况
            // 1）view[i] 还没有，直接push即可
            // 2）view[i] 已经存在，但不是最右边的值，需要将其替换
            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;
}