从前序与中序遍历序列构造二叉树 图解题解

前序和中序各自透露了什么信息

前序遍历的顺序是「根、左、右」，所以 preorder 里任何一棵子树对应的连续段，第一个元素一定是这棵子树的根——根的信息全在前序里。中序遍历的顺序是「左、根、右」，所以在 inorder 里一旦定位到根，它左边的所有值恰好组成左子树、右边的所有值恰好组成右子树——左右怎么划分的信息全在中序里。题目保证节点值互不相同，这个定位才是唯一的。

单看任何一条序列都重建不出树：前序知道谁是根却不知道左右子树的边界在哪，中序知道相对位置却不知道谁是根。两条拼在一起，信息恰好互补。

为什么这自然长成一个分治递归

拿到根、劈出左右两半之后会发现：剩下的任务「用左子树的前序和中序重建左子树」「用右子树的前序和中序重建右子树」，跟原问题一模一样，只是规模变小了。这正是分治的形状——同一套「取前序段首当根、去中序劈左右」的动作递归地做下去，直到某个中序区间为空，说明这棵子树不存在，返回 None。

preorder 那侧的切分也由中序顺手给出：设根在中序区间里左边有 k 个值，那么前序里紧跟根之后的 k 个元素就是左子树的前序，再往后是右子树的前序。实现时甚至不必显式切前序数组，维护一个全局递增的 pre 指针即可——只要坚持「先建左子树、再建右子树」，指针消费元素的顺序恰好和「根左右」对齐，每次取 preorder[self.pre] 再加一就是当前子树的根。顺序一旦颠倒成先右后左，指针取到的元素就全部错位。

哈希表为什么是复杂度的分水岭

每层递归都要回答「根在 inorder 的哪个位置」。如果每次线性扫描，单次 O(n)，n 个节点就是 O(n²)——链状树会真踩到这个最坏值。预处理一张哈希表 pos 存「值到下标」的映射，定位变成 O(1)，整体回到 O(n)。一次 O(n) 的预处理换掉递归里的重复扫描，是典型的空间换时间。

每一步为什么不会建错

正确性靠两条性质支撑：一是前序段首必为根（前序先访问根），二是中序中根两侧恰为左右子树的全部节点（中序先左后根再右）。归纳地看，只要当前段对应一棵真实子树，取出的根就是对的，劈出的两个中序区间也各自对应一棵真实子树，递归假设它们能被正确重建，拼上根就是正确的整树。区间为空返回 None 作为出口，归纳链条完整。

复杂度与常见翻车点

时间 O(n)：每个节点恰好被构造一次，找根靠哈希是 O(1)。空间 O(n)：哈希表存 n 个映射，加上递归栈 O(h)，h 为树高。

三个高频错误：左子树节点个数应是「根在中序的下标减去区间左端点」，算错则前序左右段全部切歪；先建右再建左会让 pre 指针错位（前面已说）；忘写空区间出口 inL > inR 会无限递归。变式题「中序 + 后序」同理可解——后序是「左右根」，从末尾取根、先建右再建左；而「前序 + 后序」一般不能唯一定树，因为两者都定不出单孩子在左还是在右。

Java

class Solution {
    int[] preorder;
    Map<Integer,Integer> pos = new HashMap<>(); // inorder 值 -> 下标
    int pre = 0;                                 // preorder 扫描指针

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
        return build(0, inorder.length - 1);
    }
    private TreeNode build(int inL, int inR) {
        if (inL > inR) return null;              // 空区间
        int rootVal = preorder[pre++];           // 前序首元素 = 根
        TreeNode root = new TreeNode(rootVal);
        int k = pos.get(rootVal);                // 根在 inorder 的位置
        root.left  = build(inL, k - 1);          // 先建左（前序里先出现）
        root.right = build(k + 1, inR);          // 再建右
        return root;
    }
}

Python

class Solution:
    def buildTree(self, preorder, inorder):
        pos = {v: i for i, v in enumerate(inorder)}  # 值 -> 下标
        self.pre = 0
        def build(inL, inR):
            if inL > inR:                            # 空区间
                return None
            root_val = preorder[self.pre]            # 前序首元素 = 根
            self.pre += 1
            root = TreeNode(root_val)
            k = pos[root_val]                        # 根在 inorder 的位置
            root.left  = build(inL, k - 1)           # 先建左
            root.right = build(k + 1, inR)           # 再建右
            return root
        return build(0, len(inorder) - 1)

C++

class Solution {
    vector<int> pre;
    unordered_map<int,int> pos;   // inorder 值 -> 下标
    int p = 0;                    // preorder 扫描指针
    TreeNode* build(int inL, int inR) {
        if (inL > inR) return nullptr;        // 空区间
        int rootVal = pre[p++];               // 前序首元素 = 根
        TreeNode* root = new TreeNode(rootVal);
        int k = pos[rootVal];                 // 根在 inorder 的位置
        root->left  = build(inL, k - 1);      // 先建左
        root->right = build(k + 1, inR);      // 再建右
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre = preorder;
        for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i;
        return build(0, inorder.size() - 1);
    }
};