题解 | #重建二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    map<int, int> pos;
    TreeNode* buildCore(vector<int>& pre, int pl, int pr, vector<int>& in, int il, int ir) {
        if (pl > pr) return nullptr;
        int i = pos[pre[pl]] - il;
        auto* root = new TreeNode(pre[pl]);
        root->left = buildCore(pre, pl + 1, pl + i, in, il, il + i - 1);
        root->right = buildCore(pre, pl + i + 1, pr, in, il + i + 1, ir);
        return root;
    }

    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        for (int i = 0; i < preOrder.size(); i++) pos[vinOrder[i]] = i;
        return buildCore(preOrder, 0, preOrder.size() - 1, vinOrder, 0, vinOrder.size() - 1);
    }
};