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

核心思路

· 中序遍历：[[左子树中序], 根节点, [右子树中序]]
· 后序遍历：[[左子树后序], [右子树后序], 根节点]

因此：

1. 后序遍历的最后一个元素就是根节点
2. 在中序中找到根节点的位置，左边是左子树，右边是右子树
3. 用 HashMap 预处理中序的值→下标映射，避免每次线性查找
4. 递归构建左右子树

方法一：递归 + HashMap（推荐）

class Solution {
    private Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 预处理：记录中序遍历中每个值对应的下标
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(inorder, 0, n - 1, postorder, 0, n - 1);
    }

    private TreeNode build(int[] inorder,  int inLeft,  int inRight,
                           int[] postorder, int postLeft, int postRight) {
        if (inLeft > inRight || postLeft > postRight) return null;

        // 后序最后一个元素是根
        int rootVal = postorder[postRight];
        TreeNode root = new TreeNode(rootVal);

        // 根在中序中的位置
        int inRoot = indexMap.get(rootVal);
        // 左子树节点个数
        int leftSize = inRoot - inLeft;

        // 递归构建左、右子树
        root.left = build(inorder,  inLeft,      inRoot - 1,
                          postorder, postLeft,   postLeft + leftSize - 1);
        root.right = build(inorder,  inRoot + 1,  inRight,
                           postorder, postLeft + leftSize, postRight - 1);

        return root;
    }
}

关键下标推导

设当前子树：

· 中序区间 [inLeft, inRight]
· 后序区间 [postLeft, postRight]
· 根在中序中的位置 inRoot
· 左子树节点数 leftSize = inRoot - inLeft

子树 中序区间 后序区间
左子树 [inLeft, inRoot - 1] [postLeft, postLeft + leftSize - 1]
右子树 [inRoot + 1, inRight] [postLeft + leftSize, postRight - 1]

注意：后序的最后一个位置 postRight 是根，所以右子树后序结束于 postRight - 1。

方法二：迭代法（进阶）

后序遍历的逆序是「根 → 右 → 左」，类似前序遍历的镜像。可以用栈模拟，但逻辑比 105 稍复杂。面试中递归法足够，此处仅给出思路：将 postorder 从后往前遍历，用栈记录路径，结合中序判断父子关系。若需完整实现可参考 105 的迭代法思路进行对称变换。

复杂度分析

方法 时间复杂度 空间复杂度
递归 + HashMap O(n) O(n)（哈希表 + 递归栈）
迭代法 O(n) O(h)，h 为树高

若不用 HashMap 而在中序中线性查找根，时间会退化为 O(n²)（如链状树）。

示例验证

inorder   = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]

根 = 3（后序最后一个）
中序中 3 的下标 = 1 → 左子树 [9]，右子树 [15, 20, 7]
左：中序[9] 后序[9] → 叶子 9
右：中序[15,20,7] 后序[15,7,20] → 根 20，左 15，右 7

结果：
      3
     / \
    9  20
      /  \
     15   7

输出正确 ✅

与 105 题对比

题目 根的位置 左子树后序/前序区间
105 前序 + 中序 前序第一个 前序 [preLeft+1, preLeft+leftSize]
106 中序 + 后序 后序最后一个 后序 [postLeft, postLeft+leftSize-1]

两者核心都是：用中序确定左右子树大小，用前序/后序确定根。