Construct Binary Tree from Preorder and Inorder Traversal

Q: 为什么重建二叉树需要先序遍历和中序遍历？

仅靠前序遍历无法确定树的形状。前序遍历 [1, 2] 既适用于 2 是 1 的左子节点的树，也适用于 2 是 1 的右子节点的树。中序遍历可以确定位置： [2, 1] 表示 2 在左侧， [1, 2] 表示它在右侧。值各不相同的情况下，这两种遍历结果可以唯一确定一棵树。

Q: 根据前序遍历和中序遍历构建二叉树的时间复杂度是多少？

使用从值到中序位置的映射，时间复杂度为 O(n) ，额外空间复杂度为 O(n) 。如果不使用映射，每次扫描中序范围查找根节点的代价是 O(n·h) ，对于形状像一条路径的树，这会变成 O(n²) 。

Q: 你能根据前序遍历和后序遍历重建二叉树吗？

一般来说不行。先序遍历 [1, 2] 和后序遍历 [2, 1] 既可以对应左子节点，也可以对应右子节点，因为这两种遍历都不会把根节点放在它的子树之间。只有对于每个节点都有零个或两个子节点的满二叉树，这两个遍历序列才足够。

中等树的遍历哈希递归

+10

你会得到两个数组，preorder 和 inorder，它们列出了同一棵二叉树中各不相同的值。前序遍历先访问节点，再访问它的左子树，最后访问右子树。中序遍历先访问左子树，再访问节点，最后访问右子树。

重建这棵树，并将其按层序遍历的顺序作为数组返回：根节点位于索引 0，索引 i 的子节点位于 2i+1（左）和 2i+2（右），每个空位置都用 -1 表示。数组在最后一个节点处结束，不包含末尾的 -1。

函数

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: 前序遍历中的值：节点、左子树、右子树
inorderinteger-array: 中序遍历中的值：左子树、节点、右子树
返回值integer-array: 按层序排列的树，空位置用 -1 表示，末尾不带 -1

约束条件

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴，且所有值都不相同。
inorder 中保存着相同的值，而且这两个数组描述的是同一棵二叉树。
树的深度最多为 14，因此答案中的每个索引都小于 2¹⁴-1 = 16383。

示例

输入: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
输出: [7, 3, 4, 0, 9, -1, 6]
解释: 前序遍历从根节点 7 开始。它在 inorder 中的位置是 3，所以 0, 3, 9 在左边，4, 6 在右边。4 只有一个右子节点 6，所以索引 5 保持为 -1。

输入: preorder = [1, 2, 3]inorder = [2, 3, 1]
输出: [1, 2, -1, -1, 3]
解释: 根节点 1 在 inorder 中最后出现，所以索引 2 对应 -1。在 2, 3 中，preorder 将 2 列在前面，而 inorder 将 3 放在它后面，所以 3 是它的右子节点，位于索引 4。

进阶

你能否不用递归，通过显式栈一次遍历 preorder，重建这棵树？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

先序遍历给出每棵子树的根节点：它对应区间中的第一个值。中序遍历给出分界点：根节点之前的值放在左侧，之后的值放在右侧。对两半递归，就能重建这棵树；用一个从值映射到中序位置的映射表，可以一步找到每个根节点的位置。

递归拆分，扫描根节点

思路

在前序遍历中，左子树紧跟在根节点后面，每个值占一个位置，共有 m-lo 个，其中 m 是根节点在中序遍历中的位置。右子树接在左子树后面，因此它的根节点位于 pre+1+(m-lo)。在第一个示例中，左侧部分 0, 3, 9 有 3 个值，所以右子树从前序遍历索引 4 开始，值为 4。

深度最多为 14 时，所有输出索引都小于 2^14-1。用 -1 填满这么多个单元格，将每个值写入对应索引，并在最后删去末尾的 -1 项。

扫描每个中序遍历范围来查找根节点，代价为 O(n·h)：同一层的范围不会重叠，因此每一层最多扫描 n 个项，这里最多需要 14 × 3000 = 42000 步。如果没有深度限制，形状像一条路径的树会使时间复杂度达到 O(n²)。

算法

创建包含 2^14-1 个元素的 out，所有元素都为 -1。
编写 build(pre, lo, hi, h)：如果 lo > hi，则返回。否则，将 preorder[pre] 写入 out[h]。
从 lo 开始扫描 inorder，找到根节点的位置 m。左子树有 m-lo 个值。
调用 build(pre+1, lo, m-1, 2*h+1) 和 build(pre+1+(m-lo), m+1, hi, 2*h+2)。
调用 build(0, 0, n-1, 0)，然后移除末尾的 -1 元素，并返回剩余部分。

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

使用位置映射递归拆分

思路

这些值互不相同，因此每个值在 inorder 中都恰好对应一个位置。在递归开始前，建立一个从值映射到位置的映射表，这样每次查找根节点的位置只需一步。

建立映射表需要 O(n) 时间，之后每个值只会放置一次，且操作时间为常数，因此总时间为 O(n)。映射表需要 O(n) 空间，递归则每层占用一个栈帧。在 C 和 R 中，值最大为 10^4，因此可以用一个包含 10^4+1 个元素的普通数组作为映射表。

算法

建立一个映射，将 inorder 中的每个值映射到它的位置。
创建包含 2^14-1 个元素的 out，并将它们全部设为 -1。
在 build(pre, lo, hi, h) 中，如果 lo > hi，就返回；否则，将 preorder[pre] 写入 out[h]，并在映射中查找它的位置 m。
递归调用 build(pre+1, lo, m-1, 2*h+1) 和 build(pre+1+(m-lo), m+1, hi, 2*h+2)。
调用 build(0, 0, n-1, 0)，然后删除末尾的 -1 项，并返回其余内容。

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

易错点和边界情况

从 pre+1+m 开始右子树，而不是从 pre+1+(m-lo) 开始。lo 为 0 时（例如顶层调用）可以正常工作，但起始位置较晚的范围就会出错。
忽略空隙。缺失的子节点仍会占据自己的位置，所以第二个示例的答案是 [1, 2, -1, -1, 3]，而不是 [1, 2, 3]。
保留末尾的 -1 项。返回全部 2^14-1 个单元，会让第一个示例多出 16376 个 -1 项。
每次调用都复制两个数组的切片，这会导致每层增加 O(n) 的开销。应传递索引范围。
在 Lua 和 R 中，数组从 1 开始。计算时保持位置从 0 开始，并读取 preorder[pre + 1] 和 out[h + 1]。

常见问题3

为什么重建二叉树需要先序遍历和中序遍历？

仅靠前序遍历无法确定树的形状。前序遍历 [1, 2] 既适用于 2 是 1 的左子节点的树，也适用于 2 是 1 的右子节点的树。中序遍历可以确定位置：[2, 1] 表示 2 在左侧，[1, 2] 表示它在右侧。值各不相同的情况下，这两种遍历结果可以唯一确定一棵树。

根据前序遍历和中序遍历构建二叉树的时间复杂度是多少？

使用从值到中序位置的映射，时间复杂度为 O(n)，额外空间复杂度为 O(n)。如果不使用映射，每次扫描中序范围查找根节点的代价是 O(n·h)，对于形状像一条路径的树，这会变成 O(n²)。

你能根据前序遍历和后序遍历重建二叉树吗？

一般来说不行。先序遍历 [1, 2] 和后序遍历 [2, 1] 既可以对应左子节点，也可以对应右子节点，因为这两种遍历都不会把根节点放在它的子树之间。只有对于每个节点都有零个或两个子节点的满二叉树，这两个遍历序列才足够。

def buildTree(preorder, inorder):
    # 在这里编写代码

测试 #1

测试 #2

参数

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

预期输出

[7, 3, 4, 0, 9, -1, 6]