题解 | #输出二叉树的右视图#

class Solution {
public:    
    map<int, int> pos;
    TreeNode* buildTree(vector<int>& pre, vector<int>& in, int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        int k = pos[pre[pl]] - il;
        auto* root = new TreeNode(pre[pl]);
        root->left = buildTree(pre, in, pl + 1, pl + k, il, il + k - 1);
        root->right = buildTree(pre, in, pl + k + 1, pr, il + k + 1, ir);
        return root;
    }

    void levelTravel(TreeNode* root, vector<int>& res) {
        if (!root) return;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            res.push_back(q.back()->val);
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                auto* cur = q.front();
                q.pop();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
    }

    vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {
        for (int i = 0; i < preOrder.size(); i++) pos[inOrder[i]] = i; 
        TreeNode* root = buildTree(preOrder, inOrder, 0, preOrder.size() - 1, 0, inOrder.size() - 1);
        vector<int> res;
        levelTravel(root, res);
        return res;
    }
};