题解 | #输出二叉树的右视图-修改先序遍历顺序#

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求二叉树的右视图
     * @param preOrder int整型vector 先序遍历
     * @param inOrder int整型vector 中序遍历
     * @return int整型vector
     */
    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        // write code here
        TreeNode* root = Rebuild(preOrder, inOrder);
     
        RightRecur(root, 0);

        vector<int> res;
        for (int i = 0; i <= max_depth; i++)
        {
            res.push_back(map[i]);
        }
	  
        return res;
    }

    TreeNode* Rebuild(vector<int> preOrder, vector<int> vinOrder)
    {
        int n = preOrder.size();
        int m = vinOrder.size();

        if (m == 0 || n == 0)
            return nullptr;

        TreeNode* root = new TreeNode(preOrder[0]);

        for (int i = 0; i < m; i++)
        {
            if (preOrder[0] == vinOrder[i])
            {
                vector<int> preLeft(preOrder.begin() + 1, preOrder.begin() + i + 1);
                vector<int> vinLeft(vinOrder.begin(), vinOrder.begin() + i);

                root->left = Rebuild(preLeft, vinLeft);

                vector<int> preRight(preOrder.begin() + i + 1, preOrder.end());
                vector<int> vinRight(vinOrder.begin() + i + 1, vinOrder.end());

                root->right = Rebuild(preRight, vinRight);         
            }
        }

        return root;       
    }

    int max_depth = -1;
    unordered_map<int, int> map;
    void RightRecur(TreeNode* root, int deep)
    {
        if (!root)
            return;

        RightRecur(root->right, deep + 1);
        RightRecur(root->left, deep + 1);

        if (map.find(deep) == map.end())
        {
            map[deep] = root->val;
            max_depth = max(max_depth, deep);
        }
    }
};