04 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

输入: 前序遍历 [1,2,4,7,3,5,6,8], 中序遍历 [4,7,2,1,5,3,8,6]
输出: 重建的二叉树

解题思路

核心思想：利用前序遍历的第一个元素是根节点的特性，在中序遍历中找到根节点，左右两侧分别是左子树和右子树，递归重建。

关键步骤：

1. 前序遍历的第一个元素是根节点
2. 在中序遍历中找到根节点的位置
3. 根节点左侧是左子树的中序遍历，右侧是右子树的中序遍历
4. 根据左子树长度确定前序遍历中的分割点
5. 递归构建左子树和右子树

时间复杂度：O(n)，每个节点处理一次 空间复杂度：O(n)，递归栈空间

Python 实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def reconstruct_binary_tree(preorder, inorder):
    """
    根据前序遍历和中序遍历重建二叉树

    Args:
        preorder: 前序遍历序列
        inorder: 中序遍历序列

    Returns:
        TreeNode: 重建的二叉树根节点
    """
    if not preorder or not inorder:
        return None

    # 前序遍历的第一个元素是根节点
    root_val = preorder[0]
    root = TreeNode(root_val)

    # 在中序遍历中找到根节点的位置
    root_idx = inorder.index(root_val)

    # 递归构建左子树和右子树
    root.left = reconstruct_binary_tree(
        preorder[1:root_idx + 1],
        inorder[:root_idx]
    )
    root.right = reconstruct_binary_tree(
        preorder[root_idx + 1:],
        inorder[root_idx + 1:]
    )

    return root


# 优化版本：使用字典加速查找
def reconstruct_binary_tree_optimized(preorder, inorder):
    """
    优化版本：使用字典存储中序遍历的值到索引的映射
    """
    if not preorder or not inorder:
        return None

    # 建立中序遍历的值到索引的映射
    inorder_map = {val: idx for idx, val in enumerate(inorder)}

    def build(pre_start, pre_end, in_start, in_end):
        if pre_start > pre_end or in_start > in_end:
            return None

        root_val = preorder[pre_start]
        root = TreeNode(root_val)

        # 在中序遍历中找到根节点的位置
        root_idx = inorder_map[root_val]

        # 计算左子树的长度
        left_size = root_idx - in_start

        root.left = build(pre_start + 1, pre_start + left_size,
                          in_start, root_idx - 1)
        root.right = build(pre_start + left_size + 1, pre_end,
                           root_idx + 1, in_end)

        return root

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


# 辅助函数：中序遍历
def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)


# 测试代码
if __name__ == "__main__":
    preorder = [1, 2, 4, 7, 3, 5, 6, 8]
    inorder = [4, 7, 2, 1, 5, 3, 8, 6]

    root = reconstruct_binary_tree(preorder, inorder)
    print(inorder_traversal(root))  # [4, 7, 2, 1, 5, 3, 8, 6]

    root2 = reconstruct_binary_tree_optimized(preorder, inorder)
    print(inorder_traversal(root2))  # [4, 7, 2, 1, 5, 3, 8, 6]

图解

前序遍历: [1, 2, 4, 7, 3, 5, 6, 8]
中序遍历: [4, 7, 2, 1, 5, 3, 8, 6]

步骤1: 根节点 = 1
        中序中1的位置: 3
        左子树中序: [4, 7, 2], 右子树中序: [5, 3, 8, 6]

步骤2: 递归处理左子树
        前序: [2, 4, 7], 中序: [4, 7, 2]
        根节点 = 2, 左子树: [4, 7], 右子树: []

步骤3: 继续递归...
        最终得到二叉树:
            1
           / \
          2   3
         /   / \
        4   5   6
         \       \
          7       8