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

约 5 分钟
文章信息 15 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 面试经典 150 题 腾讯 字节 阿里 美团 小米 百度 网易 虾皮 旷视
标签
数组 哈希表 树 二叉树 分治

题目描述

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

image-20260928204002772

image-20260928204002773

题意分析

给定同一棵二叉树的中序遍历与后序遍历，重新构造它的节点和左右孩子关系，并返回根节点。中序顺序为左子树、根、右子树，后序顺序为左子树、右子树、根。

题目保证两组序列有效、长度相同，节点值互不相同，因此每个值在中序中的位置唯一，树的结构也能被唯一确定。不能把中序误当成排序后的结果，原树并不要求是二叉搜索树。

解法：哈希表定位根节点递归建树

核心思路

[!blue]

一棵子树的后序遍历最后一个元素就是它的根。在中序中找到这个根的位置后，根左边的连续区间全部属于左子树，右边的连续区间全部属于右子树。对这两个区间继续使用相同规则，就能逐层恢复结构。

如果从整个后序数组的末尾往前读，顺序会变成根、右子树、左子树。因此可以用共享的 postIndex 指向下一个尚未使用的节点值，递归只传当前子树的中序闭区间 [inLeft, inRight]，不必额外复制或切分后序数组。

每次非空调用从 postorder[postIndex] 取根并递减游标，查出根的中序位置 rootIndex，然后必须先构造右区间，再构造左区间。右子树的调用会恰好消费它对应的所有节点，返回时游标才停在左子树根的位置；如果交换这两个递归调用，游标仍指向右子树的数据，却会被当成左子树节点。

当 inLeft > inRight 时，当前区间没有节点，应立即返回空，且不能消费后序游标。单个位置的区间则仍要创建一个真实节点，再由两个空区间结束其孩子调用。每个根都把问题缩成更小的区间，递归最终到达这些边界。

先建立“节点值到中序下标”的哈希表，避免每次寻找根时重新扫描中序区间。Java 实现把索引表、后序数组和游标存成字段，但在每次入口调用都重新初始化；Go 用本次调用的局部变量和闭包保存状态，所以多次调用不会复用上次的游标。

解题步骤

  1. 遍历中序数组，建立值到下标的映射，将后序游标置于最后一个元素。
  2. 从整个中序闭区间调用构造函数；空区间直接返回空节点。
  3. 读取并消费一个后序值，创建根节点，查出它在中序区间中的分界位置。
  4. 先递归构造 [rootIndex + 1, inRight] 作为右子树，再构造 [inLeft, rootIndex - 1] 作为左子树。
  5. 返回连接好两个孩子的根节点，直到顶层返回整棵树。

代码实现

class Solution {
    private Map<Integer, Integer> indexMap;
    private int[] postorder;
    private int postIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        indexMap = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }

        postIndex = postorder.length - 1;

        return build(0, inorder.length - 1);
    }

    private TreeNode build(int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }

        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = indexMap.get(rootVal);

        // 后序倒着读是根、右、左，必须先消费右子树。
        root.right = build(rootIndex + 1, inRight);
        root.left = build(inLeft, rootIndex - 1);

        return root;
    }
}

func buildTree(inorder []int, postorder []int) *TreeNode {
    indexMap := make(map[int]int)
    for i, value := range inorder {
        indexMap[value] = i
    }

    postIndex := len(postorder) - 1
    var build func(int, int) *TreeNode
    build = func(inLeft int, inRight int) *TreeNode {
        if inLeft > inRight {
            return nil
        }

        rootVal := postorder[postIndex]
        postIndex--
        root := &TreeNode{Val: rootVal}
        rootIndex := indexMap[rootVal]
        // 后序倒着读是根、右、左，必须先消费右子树。
        root.Right = build(rootIndex+1, inRight)
        root.Left = build(inLeft, rootIndex-1)
        return root
    }
    return build(0, len(inorder)-1)
}

复杂度分析

  • 时间复杂度：$O(n)$，建表处理每个元素一次，递归创建每个节点一次，哈希查找按期望常数时间计算。
  • 空间复杂度：$O(n)$，索引表保存 n 个位置，递归栈占 $O(h)$，最坏树高为 n；不计返回树本身。

关键点总结

[!green]

  • 后序末尾决定根，中序中的唯一根位置决定左右子树范围。
  • 共享游标倒序消费后序，递归构造顺序必须跟随根、右、左。
  • 中序区间决定当前调用应消费多少节点，空区间不能提前移动游标。
  • 哈希定位和传下标避免重复扫描与复制子数组。

易错点总结

[!yellow]

  • 使用递减的后序游标却先构造左子树，会把下一段右子树数据装入错误的区间。
  • 把递归出口写成 inLeft >= inRight，会跳过所有单节点子树；只有左端大于右端才为空。
  • 在空区间判断前读取后序元素，会错误消耗游标，后续可能错位或越界。
  • 递归区间再次包含根位置，无法按正确规模缩小，也会重复消费节点。
  • 忽略值唯一的前提，哈希表会覆盖重复值下标，原有划分依据不再成立。
  • 字段状态不在入口重置，会让同一对象后续调用使用旧数组或旧游标。

相似题目

题目 难度 关联与区别
105. 从前序与中序遍历序列构造二叉树 中等 两题都在中序定位根并切分子树，根在另一个序列中的位置不同。
297. 二叉树的序列化与反序列化 困难 序列化通过空位标记保留结构，本题通过中序与后序的对应关系恢复结构。
889. 从前序与后序遍历序列构造二叉树 中等 用遍历序列中的根位置划分左右子树；本题由后序末尾根划分中序区间，该题以前序次项定位后序中的左子树边界。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/66276999
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！