重建二叉树 - JZ04

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

限制： 0 ≤ 节点个数 ≤ 5000

样例：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

解题思路

这道题是经典的分治递归问题，关键是理解前序遍历和中序遍历的特点：

1. 前序遍历特点： 根节点总是第一个元素
2. 中序遍历特点： 根节点将数组分为左子树和右子树两部分
3. 分治思想： 递归地构建左子树和右子树

算法步骤：

1. 从前序遍历中取第一个元素作为根节点
2. 在中序遍历中找到根节点的位置，分割左右子树
3. 递归构建左子树和右子树
4. 返回根节点

优化方案：

• 使用哈希表存储中序遍历的值和索引，提高查找效率

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 二叉树类型定义和工具函数
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── main.go             # 主函数和测试用例
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现以下函数：

• buildTree(preorder []int, inorder []int) *TreeNode - 主要实现

可选优化实现：

• buildTreeWithMap(preorder []int, inorder []int) *TreeNode - 使用哈希表优化

2. 运行测试

# 运行主程序，查看测试结果
go run .

# 运行单元测试
go test -v

# 运行基准测试
go test -bench=.

3. 检查代码格式

# 格式化代码
go fmt ./...

# 代码检查
go vet ./...

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
基础递归	O(n²)	O(n)	每次查找根节点需要O(n)
哈希表优化	O(n)	O(n)	预处理中序遍历索引

其中 n 是树中节点的个数。

知识点

• 二叉树的遍历（前序、中序、后序）
• 分治算法思想
• 递归的应用
• 哈希表的使用
• 数组切片操作

相关题目

• 根据中序和后序遍历重建二叉树
• 二叉树的序列化与反序列化
• 验证二叉搜索树的后序遍历序列