105. 从前序与中序遍历序列构造二叉树

难度：🟡 Medium | 标签：树、递归、哈希 | 状态：⬜ LeetCode 链接

思路

前序首元素是根。中序里找到根位置，左侧是左子的中序、右侧是右子的中序。

用哈希 值 → 中序下标 把 O(n²) 优化到 O(n)。 递归参数：前序区间 + 中序区间。

代码

class Solution {
    unordered_map<int, int> idx;
    vector<int> pre, in;
    TreeNode* build(int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        int rootVal = pre[pl];
        int m = idx[rootVal];
        int leftSize = m - il;
        auto* root = new TreeNode(rootVal);
        root->left  = build(pl + 1, pl + leftSize, il, m - 1);
        root->right = build(pl + leftSize + 1, pr, m + 1, ir);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre = preorder; in = inorder;
        for (int i = 0; i < (int)in.size(); ++i) idx[in[i]] = i;
        return build(0, pre.size() - 1, 0, in.size() - 1);
    }
};

复杂度

• 时间 O(n)（有哈希），空间 O(n)

易错 / 回顾

• 区间长度 leftSize = m - il，前序分段时 pl + leftSize
• 假定所有节点值不同（题目保证）
• 后序+中序（106）同套路，根在后序末尾