从前中后序构造二叉树——哈希加速与递归边界

适读人群：Java 后端工程师、准备面试的同学 | 阅读时长：约22分钟 | 难度：Medium

---

开篇故事

105 题（前序+中序构造）和 106 题（中序+后序构造）是我做过的树的题目里，最需要"想清楚再动手"的两道。

初次接触时，感觉思路很清晰：前序第一个元素是根，在中序里找到根的位置，左边是左子树，右边是右子树，然后递归。听起来很简单，但一动手写，索引就开始乱——前序数组的哪个范围对应左子树？中序数组的哪个范围对应右子树？递归边界是什么？

我当时就是靠死算了几个例子才把索引关系搞清楚。后来发现，用哈希表预存中序索引，再加上把索引推导写得足够清晰，这道题可以写得非常优雅。

这篇文章重点在索引推导——把每一个索引是怎么算出来的都写清楚，不留含糊。

---

一、题目解析

题目一：LeetCode 105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

题目二：LeetCode 106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历，请构造并返回这颗二叉树的根节点。

示例：

前序：[3,9,20,15,7]，中序：[9,3,15,20,7]
输出：[3,9,20,null,null,15,7]

中序：[9,3,15,20,7]，后序：[9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

考点梳理：

1. 前序、中序、后序遍历序列的结构特征
2. 从根节点位置推导左右子树的范围
3. 用哈希表优化中序查找（从 O(n) 降到 O(1)）
4. 递归的参数设计和边界条件

---

二、解法一：暴力解法——每次线性查找根节点在中序的位置

思路（以 105 前序+中序为例）

每次从前序数组取第一个元素作为根，然后在中序数组中线性查找根节点位置，确定左右子树大小，递归处理。

缺点：每次查找是 O(n)，总时间 O(n^2)。

完整代码（105）

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length - 1,
                     inorder, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int preLeft, int preRight,
                           int[] in, int inLeft, int inRight) {
        if (preLeft > preRight) return null;
        
        // 前序第一个元素是根
        int rootVal = pre[preLeft];
        TreeNode root = new TreeNode(rootVal);
        
        // 在中序数组中线性查找根的位置
        int inRoot = inLeft;
        while (in[inRoot] != rootVal) inRoot++;
        
        // 左子树的节点数
        int leftSize = inRoot - inLeft;
        
        // 递归构建左右子树
        root.left = build(pre, preLeft + 1, preLeft + leftSize,
                          in, inLeft, inRoot - 1);
        root.right = build(pre, preLeft + leftSize + 1, preRight,
                           in, inRoot + 1, inRight);
        
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n^2)。每次查找 O(n)，共 n 个节点。
• 空间复杂度：O(n)。递归栈深度 O(n)。

---

三、解法二：哈希表优化查找（105 前序+中序）

思路

用 HashMap 预存中序数组中每个值到其索引的映射，查找时 O(1)，总时间降到 O(n)。

索引推导（关键）：

设当前前序范围 [preLeft, preRight]，中序范围 [inLeft, inRight]：

• 根节点值：pre[preLeft]
• 根节点在中序中的位置：inRoot = inorderMap.get(pre[preLeft])
• 左子树节点数：leftSize = inRoot - inLeft
• 前序左子树范围：[preLeft+1, preLeft+leftSize]
• 前序右子树范围：[preLeft+leftSize+1, preRight]
• 中序左子树范围：[inLeft, inRoot-1]
• 中序右子树范围：[inRoot+1, inRight]

完整代码

class Solution {
    private Map<Integer, Integer> inorderMap;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return null;
        
        int rootVal = pre[preLeft];
        int inRoot = inorderMap.get(rootVal);
        int leftSize = inRoot - inLeft;
        
        TreeNode root = new TreeNode(rootVal);
        root.left = build(pre, preLeft + 1, preLeft + leftSize, inLeft, inRoot - 1);
        root.right = build(pre, preLeft + leftSize + 1, preRight, inRoot + 1, inRight);
        
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n)。哈希表查找 O(1)，每个节点处理一次。
• 空间复杂度：O(n)。哈希表 O(n)，递归栈 O(n)。

---

四、解法三：最优解法——中序+后序构造（106）及迭代实现

中序+后序构造（106）

和前序+中序类似，区别是根节点在后序数组的最后一个位置。

索引推导：

• 根节点值：post[postRight]
• 根节点在中序中的位置：inRoot
• 左子树节点数：leftSize = inRoot - inLeft
• 后序左子树范围：[postLeft, postLeft+leftSize-1]
• 后序右子树范围：[postLeft+leftSize, postRight-1]
• 中序左子树范围：[inLeft, inRoot-1]
• 中序右子树范围：[inRoot+1, inRight]

Mermaid 图——索引分配关系

完整代码（106）

class Solution {
    private Map<Integer, Integer> inorderMap;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(postorder, 0, postorder.length - 1, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] post, int postLeft, int postRight, int inLeft, int inRight) {
        if (postLeft > postRight) return null;
        
        // 后序最后一个元素是根
        int rootVal = post[postRight];
        int inRoot = inorderMap.get(rootVal);
        int leftSize = inRoot - inLeft;
        
        TreeNode root = new TreeNode(rootVal);
        root.left = build(post, postLeft, postLeft + leftSize - 1, inLeft, inRoot - 1);
        root.right = build(post, postLeft + leftSize, postRight - 1, inRoot + 1, inRight);
        
        return root;
    }
}

迭代版本（105，使用栈）

迭代实现利用前序和中序数组的对应关系：前序依次给出"当前要处理的节点"，中序的位置决定"是否应该往左还是往右建立连接"。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        int inorderIdx = 0;  // 中序数组的指针
        
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = stack.peek();
            TreeNode newNode = new TreeNode(preorder[i]);
            
            // 如果栈顶节点不等于中序当前元素，新节点是栈顶节点的左子节点
            if (node.val != inorder[inorderIdx]) {
                node.left = newNode;
            } else {
                // 弹出已处理完左子树的节点，直到找到应该作为父节点的节点
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIdx]) {
                    node = stack.pop();
                    inorderIdx++;
                }
                node.right = newNode;
            }
            
            stack.push(newNode);
        }
        
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n)。每个节点入出栈一次。
• 空间复杂度：O(n)。栈空间 O(h)，最坏 O(n)。

提交结果：时间击败约 99% 用户，空间击败约 70% 用户。

---

五、举一反三

同类题目

LeetCode 889. 根据前序和后序遍历构造二叉树 前序+后序构造，注意这种组合不唯一（不能确定单子节点是左还是右），需要做一个选择。

LeetCode 1008. 前序遍历构造二叉搜索树 只用前序序列构造 BST（因为 BST 的结构由前序唯一确定）。

索引推导速查表

105（前序+中序）：

• 根：pre[preLeft]
• 左子树大小：leftSize = inRoot - inLeft
• 前序左范围：[preLeft+1, preLeft+leftSize]
• 前序右范围：[preLeft+leftSize+1, preRight]

106（中序+后序）：

• 根：post[postRight]
• 左子树大小：leftSize = inRoot - inLeft
• 后序左范围：[postLeft, postLeft+leftSize-1]
• 后序右范围：[postLeft+leftSize, postRight-1]

---

六、踩坑实录

坑一：后序左子树范围的右边界差一

105 前序左子树范围是 [preLeft+1, preLeft+leftSize]，注意右边界是 preLeft+leftSize（包含）。

106 后序左子树范围是 [postLeft, postLeft+leftSize-1]，注意右边界要减 1。

这里差一错误是最常见的 bug。建议用小例子（3个节点的树）验证一遍索引是否正确。

坑二：哈希表的 key 是值，但题目保证值唯一吗？

题目约束写明了"树中不存在重复节点"，所以用值做 key 是安全的。如果值可以重复，这个方法就不能用了，需要换路径记录的方式。

坑三：递归终止条件写成 preLeft >= preRight

正确终止条件是 preLeft > preRight（严格大于），等于时还有一个节点需要处理。这个写错了，单节点的子树会返回 null，导致整棵树缺失叶子节点。

坑四：后序根节点索引用 post[postRight] 而不是 post[post.length-1]

每次递归的根节点是当前后序范围的最后一个元素 post[postRight]，而不是整个后序数组的最后一个元素。索引要跟随递归范围变动。

坑五：迭代版本不理解为什么比较 inorder[inorderIdx]

迭代版本的核心思路：前序是"根-左子树-右子树"，中序是"左子树-根-右子树"。当前序遍历到某个节点 A，而中序指针也指向 A 时，说明 A 的左子树已经处理完，下一个前序节点应该接在 A 的右边（或 A 的某个祖先的右边）。这个对应关系需要结合模拟才能真正理解。

---

七、总结

105 和 106 题的核心挑战是索引推导的准确性。建议动手在纸上画一棵 4-5 个节点的树，写出它的前序、中序、后序序列，然后手动模拟索引的切分过程，一旦把索引关系吃透了，代码就很好写了。

哈希表优化是从 O(n^2) 到 O(n) 的关键一步，在实际代码里这个优化很重要。迭代版本展示了另一种思路——用栈模拟前序遍历的过程，根据中序指针来决定连接方向。

这两道题还告诉我们一个重要的算法知识：前序+中序或后序+中序可以唯一确定一棵二叉树，但前序+后序不行（因为无法确定哪些节点属于左子树）。这个结论在数据序列化/反序列化的设计中有实际意义。