分治：构建二叉树问题

一、介绍

给定一个二叉树的前序遍历preorder 和中序遍历 inorder ，请从中构建二叉树，返回二叉树的根节点。

1. 判断是否为分治问题

原问题定义为从 preorder 和 inorder 构建二叉树，其是一个典型的分治问题。

‧ 问题可以被分解：从分治的角度切入，我们可以将原问题划分为两个子问题：构建左子树、构建右子 树，加上一步操作：初始化根节点。而对于每个子树（子问题），我们仍然可以复用以上划分方法，将 其划分为更小的子树（子问题），直至达到最小子问题（空子树）时终止。

‧ 子问题是独立的：左子树和右子树是相互独立的，它们之间没有交集。在构建左子树时，我们只需要关 注中序遍历和前序遍历中与左子树对应的部分。右子树同理。

‧ 子问题的解可以合并：一旦得到了左子树和右子树（子问题的解），我们就可以将它们链接到根节点上， 得到原问题的解。

2. 如何划分子树

根据以上分析，这道题是可以使用分治来求解的，但如何通过前序遍历 左子树和右子树呢？ 根据定义， preorder 和 inorder 都可以被划分为三个部分。

‧ 前序遍历： preorder 和中序遍历 inorder 来划分 [ 根节点 | 左子树 | 右子树 ]，例如图的树对应 [ 3 | 9 | 2 1 7 ]。

‧ 中序遍历： [ 左子树 | 根节点 ｜ 右子树 ]，例如图的树对应 [ 9 | 3 | 1 2 7 ]。

以上图数据为例，我们可以通过下图所示的步骤得到划分结果。

1. 前序遍历的首元素3是根节点的值。

2. 查找根节点3在 inorder 中的索引，利用该索引可将 inorder 划分为 [ 9 | 3 ｜ 1 2 7 ]。

3. 根据inorder 划分结果，易得左子树和右子树的节点数量分别为1和3，从而可将 preorder 划分为 [ 3 | 9 | 2 1 7 ]。

3. 基于变量描述子树区间

根据以上划分方法，我们已经得到根节点、左子树、右子树在述这些索引区间，我们需要借助几个指针变量。

‧ 将当前树的根节点在preorder 中的索引记为𝑖。

‧ 将当前树的根节点在inorder 中的索引记为𝑚。

‧ 将当前树在inorder 中的索引区间记为[𝑙,𝑟]。

如表所示，通过以上变量即可表示根节点在 preorder 中的索引，以及子树在inorder 中的索引区间。

请注意，右子树根节点索引中的(𝑚−𝑙)的含义是“左子树的节点数量”。配合下图理解。

二、代码实现

为了提升查询𝑚的效率，我们借助一个哈希表hmap 来存储数组inorder 中元素到索引的映射。

import sys
from pathlib import Path

sys.path.append(str(Path(__file__).parent.parent))
from modules import TreeNode, print_tree


def dfs(
    preorder: list[int],
    inorder_map: dict[int, int],
    i: int,
    l: int,
    r: int,
) -> TreeNode | None:
    """构建二叉树：分治"""
    # 子树区间为空时终止
    if r - l < 0:
        return None
    # 初始化根节点
    root = TreeNode(preorder[i])
    # 查询 m ，从而划分左右子树
    m = inorder_map[preorder[i]]
    # 子问题：构建左子树
    root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
    # 子问题：构建右子树
    root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
    # 返回根节点
    return root


def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    """构建二叉树"""
    # 初始化哈希表，存储 inorder 元素到索引的映射
    inorder_map = {val: i for i, val in enumerate(inorder)}
    root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
    return root


"""Driver Code"""
if __name__ == "__main__":
    preorder = [3, 9, 2, 1, 7]
    inorder = [9, 3, 1, 2, 7]
    print(f"前序遍历 = {preorder}")
    print(f"中序遍历 = {inorder}")

    root = build_tree(preorder, inorder)
    print("构建的二叉树为：")
    print_tree(root)

输出：

每个递归函数内的前序遍历 preorder 和中序遍历 inorder 的划分结果如图所示。

设树的节点数量为𝑛，初始化每一个节点（执行一个递归函数dfs() ）使用𝑂(1)时间。因此总体时间复杂度为𝑂(𝑛)。
哈希表存储inorder 元素到索引的映射，空间复杂度为𝑂(𝑛)。最差情况下，即二叉树退化为链表时，递归深度达到𝑛，使用𝑂(𝑛)的栈帧空间。因此总体空间复杂度为𝑂(𝑛)。