1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution
{
public:
    std::unordered_map<int, int> pos; // 中序遍历中值到索引的映射

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        // 建立中序遍历的值索引映射，方便快速定位根节点位置
        for (int i = 0; i < inorder.size(); ++i)
            pos[inorder[i]] = i;

        // 调用递归构造函数
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* build(std::vector<int>& preorder, std::vector<int>& inorder, int pl, int pr, int il, int ir)
    {
        if (pl > pr) // 如果前序区间为空，返回空节点
            return nullptr;

        // 当前子树的根节点
        TreeNode* root = new TreeNode(preorder[pl]);

        // 根节点在中序遍历中的位置
        int k = pos[root->val];

        // 递归构造左子树
        root->left = build(preorder, inorder, pl + 1, pl + 1 + k - 1 - il, il, k - 1);

        // 递归构造右子树
        root->right = build(preorder, inorder, pl + 1 + k - 1 - il + 1, pr, k + 1, ir);

        return root;
    }
};