LeetCode 剑指 Offer 07. 重建二叉树

2023-05-10 HGNULB 约 5 分钟

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

分类

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

标签

数组 哈希表 树 二叉树 分治

题目描述

✅ 剑指 Offer 07. 重建二叉树

题意分析

给出同一棵二叉树的前序遍历和中序遍历，重新创建这棵树并返回根节点。前序顺序为“根、左子树、右子树”，中序顺序为“左子树、根、右子树”。

题目保证节点值不重复，输入是这棵树的合法遍历结果。目标不仅是还原全部节点值，还要还原每个节点的左右孩子关系；空遍历对应空树。值互不相同，使一个根在中序中的位置唯一，左右范围也就能够唯一确定。

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

核心思路

[!blue]

对任意一棵待构造的子树，前序片段的第一个值一定是根。找到它在中序中的位置后，左边全部属于左子树，右边全部属于右子树。中序负责确定子树包含哪些节点，前序负责指出每棵子树的根是谁。

定义 build(preRoot, inLeft, inRight)：当前子树的根位于前序下标 preRoot，全部节点对应中序闭区间 [inLeft, inRight]。设根的中序下标为 inRoot，左子树节点数就是 leftSize = inRoot - inLeft。

前序先列根，再完整列出左子树，最后列出右子树。因此左子树的前序根为 preRoot + 1，中序范围为 [inLeft, inRoot - 1]；右子树要跳过根以及全部 leftSize 个左侧节点，前序根为 preRoot + leftSize + 1，中序范围为 [inRoot + 1, inRight]。

左右子问题使用同一规则继续划分，各自返回根后挂到当前根的两侧。中序区间为空时返回空指针，单点区间仍要创建一个真实节点。必须先检查空区间，再读取前序值，因为空子树传入的前序下标不需要指向有效元素。

预先建立“节点值到中序下标”的哈希表，避免每层重复查找。递归只传递下标，共享原数组，不复制子数组；每个节点恰好被创建一次。

解题步骤

1. 遍历中序数组，建立节点值到其下标的映射。
2. 从前序根下标 0、中序区间 [0, n - 1] 开始构造。
3. 中序左界大于右界时返回空，否则读取前序根值，查出其中序位置并创建节点。
4. 根据 inRoot - inLeft 求左子树大小，分别计算左右子树的前序根下标和中序范围。
5. 递归构造左右孩子，连接到当前节点后返回当前根。

代码实现

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(h)$，链状树最坏为 $O(n)$；返回的新树属于输出空间。

关键点总结

[!green]

• 前序首项确定根，中序根的位置确定两边节点范围，两种顺序共同决定结构。
• 当前区间内的左子树大小连接了两套下标，不能把中序的全局位置直接当作大小。
• 右侧前序根需要跳过当前根与整棵左子树，左侧前序根只跳过当前根。
• 值唯一保证查表无歧义，下标递归保证不重复扫描和复制子数组。

易错点总结

[!yellow]

• 右子树根下标少加一，把当前根占用的位置漏算，导致之后的前序划分全部错位。
• 用 inRoot 直接表示左子树大小，进入左界不为零的子区间时会算错；应减去 inLeft。
• 将结束条件写成 inLeft >= inRight，会把只有一个节点的合法子树也当成空树。
• 在判断空区间前读取前序下标，空子树可能触发越界。
• 每层从头扫描中序或复制子数组，会使链状树的累计处理量退化到平方级。
• 忽略节点值互异的前提，重复值不能用单个下标映射唯一确定当前切分位置。

相似题目

题目	难度	关联与区别
106. 从中序与后序遍历序列构造二叉树	中等	中序仍负责划分左右子树，原题从后序末尾取根，本题从前序开头取根。
889. 从前序与后序遍历序列构造二叉树	中等	只给前序和后序可能无法唯一确定左右孩子，本题有中序且值互异时分割位置唯一。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/67552711

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！