LeetCode 剑指 Offer 07. 重建二叉树

2023-05-10 HGNULB 约 6 分钟

文章信息 10 个分类 · 5 个标签

分类

LeetCode CodeTop 中等 未解决 10-20 字节跳动 阿里巴巴 拼多多 剑指 Offer 剑指 Offer（第 2 版）

标签

数组 哈希表 树 二叉树 分治

目录 收起 展开

题目描述

✅ 剑指 Offer 07. 重建二叉树

题意分析

给出同一棵二叉树的前序遍历数组 preorder 和中序遍历数组 inorder，要求把这棵树重新造出来，返回根节点。

之所以只给两个数组就能唯一确定一棵树，是因为这两种遍历各自携带了互补的信息：前序遍历的规则是「根 → 左子树 → 右子树」，所以一段前序区间的第一个值必定是这棵子树的根；中序遍历的规则是「左子树 → 根 → 右子树」，所以在中序数组里根的左边全是左子树的节点、右边全是右子树的节点。前者告诉我们「根是谁」，后者告诉我们「左右子树各有多少个节点、分别是哪些」。

约束信号有两条很关键。一是题目保证节点值互不相同，这让「拿一个值去中序数组里找位置」的结果唯一，否则左右子树的切分就会有歧义。二是节点数量上限 5000，看上去不大，但树可能退化成一条链，如果每层都去中序数组里线性扫一遍找根，总量就是 $5000^2$ 级别，这正是题目暗藏的效率考点。

边界情况：数组为空时返回空节点；只有一个节点；整棵树退化成全左链（前序 [3,2,1]、中序 [1,2,3]）或全右链（前序与中序完全相同）。

解法：前序定位根，中序划分子树

核心思路

前序遍历的顺序是“根、左、右”，所以当前子树的前序首元素一定是根；中序遍历的顺序是“左、根、右”，根在中序中的位置可以确定左右子树的范围。

为避免每层递归都在线性扫描中序数组，先建立“节点值到中序下标”的哈希表。递归参数使用当前根在前序中的下标 preRoot，以及当前子树在中序中的闭区间 [inLeft, inRight]。

设根在中序中的位置为 inRoot，左子树节点数为 leftSize = inRoot - inLeft：

• 左子树的前序根下标是 preRoot + 1，中序区间是 [inLeft, inRoot - 1]。
• 右子树前面要跳过根和整个左子树，因此前序根下标是 preRoot + leftSize + 1，中序区间是 [inRoot + 1, inRight]。

不变量与正确性：每次递归中，preRoot 指向当前中序区间所描述子树的根。前序首元素确定根，中序位置唯一划分左右节点集合，计算出的两个前序根下标又分别落在左右子树首部。对区间长度归纳，可知递归会还原每个节点及其左右关系。

解题步骤

• 遍历 inorder，建立 value -> index 哈希表。
• 从 preRoot = 0、中序区间 [0, n-1] 开始递归。
• 若 inLeft > inRight，当前区间为空，返回 null。
• 用 preorder[preRoot] 创建根节点，并在哈希表中找到 inRoot。
• 根据 leftSize 计算左右子树的前序根下标和中序范围，递归构造后挂到根节点。
• 返回根节点。

例如前序 [3,9,20,15,7]、中序 [9,3,15,20,7]：根 3 在中序下标 1，左侧 1 个节点，因此左根是前序下标 1 的 9，右根是前序下标 0 + 1 + 1 = 2 的 20；对子区间重复同样过程即可。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            index.put(inorder[i], i);
        }
        return build(preorder, 0, 0, inorder.length - 1, index);
    }

    private TreeNode build(int[] preorder, int preRoot, int inLeft,
                           int inRight, Map<Integer, Integer> index) {
        if (inLeft > inRight) {
            return null;
        }

        int rootValue = preorder[preRoot];
        int inRoot = index.get(rootValue);
        int leftSize = inRoot - inLeft;

        TreeNode root = new TreeNode(rootValue);
        root.left = build(preorder, preRoot + 1,
                inLeft, inRoot - 1, index);
        root.right = build(preorder, preRoot + leftSize + 1,
                inRoot + 1, inRight, index);
        return root;
    }
}

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

    var build func(int, int, int) *TreeNode
    build = func(preRoot, inLeft, inRight int) *TreeNode {
        if inLeft > inRight {
            return nil
        }

        rootValue := preorder[preRoot]
        inRoot := index[rootValue]
        leftSize := inRoot - inLeft

        root := &TreeNode{Val: rootValue}
        root.Left = build(preRoot+1, inLeft, inRoot-1)
        root.Right = build(preRoot+leftSize+1, inRoot+1, inRight)
        return root
    }

    return build(0, 0, len(inorder)-1)
}

复杂度分析

• 时间复杂度：$O(n)$。建立哈希表和创建全部节点各遍历一次，每次定位根为 $O(1)$。
• 空间复杂度：$O(n)$。哈希表占 $O(n)$，递归栈最坏在链状树中占 $O(n)$；返回的树不计入额外空间。

关键点总结

• 前序负责确定根，中序负责确定左右子树的节点范围。
• 节点值互不相同，才能用一张哈希表唯一定位根。
• leftSize = inRoot - inLeft 是连接两种遍历区间的关键。
• 右子树的前序根要同时跳过当前根和左子树，即 preRoot + leftSize + 1。
• 传下标而不是复制子数组，才能保持线性时间和较低额外开销。

易错点总结

• 右子树下标少加 1：会再次把左子树节点当成右根；必须跳过当前根。
• 把 leftSize 写成 inRoot：递归进入右侧区间后，inLeft 不再是 0，子树大小会算错。
• 终止条件写成 inLeft >= inRight：单节点区间会被直接丢弃，正确条件是 inLeft > inRight。
• 每层扫描中序数组或复制切片：链状树会退化为 $O(n^2)$。
• 忽略值唯一的前提：有重复值时，单个“值到下标”的映射不足以确定切分位置。

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	与本题完全同题，可直接复用同一份区间递归代码
106. 从中序与后序遍历序列构造二叉树	中等	根改为后序区间的最后一个元素，切分方向随之镜像
889. 从前序与后序遍历序列构造二叉树	中等	缺少中序导致答案不唯一，需要靠左子树根来定位分界
108. 将有序数组转换为二叉搜索树	简单	有序数组即中序序列，取中点为根以保证树高平衡
109. 有序链表转换二叉搜索树	中等	链表无法随机访问，需用快慢指针找中点或按中序顺序自底构造
297. 二叉树的序列化与反序列化	困难	反向问题：设计一种能靠单个序列唯一还原的编码
面试题 04.02. 最小高度树	简单	只要求高度最小而不要求还原特定形状，构造结果不唯一