树的子结构 - JZ17

题目描述

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

注意： 约定空树不是任意一个树的子结构

B 是 A 的子结构， 即 A 中有出现和 B 相同的结构和节点值。

示例：

给定的树 A:

     3
    / \
   4   5
  / \
 1   2

给定的树 B：

   4 
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

• 输入：A = [1,2,3], B = [3,1]
• 输出：false

示例 2：

• 输入：A = [3,4,5,1,2], B = [4,1]
• 输出：true

限制：

• 0 <= 节点个数 <= 10000

解题思路

这道题需要用到双重递归的思想：

1. 外层递归： 遍历树 A 的每个节点，找到与树 B 根节点值相等的节点
2. 内层递归： 对于找到的节点，判断以该节点为根的子树是否包含 B

核心思路

• 如果 B 为空，则 B 不是任何树的子结构（题目约定）
• 如果 A 为空但 B 不为空，则 B 不是 A 的子结构
• 否则：
  • 如果当前节点匹配，检查以当前节点为根的子树是否匹配 B
  • 递归检查 A 的左子树是否包含 B
  • 递归检查 A 的右子树是否包含 B

项目结构

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

使用方法

1. 实现算法

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

• isSubStructure(A *TreeNode, B *TreeNode) bool - 主函数：判断 B 是否是 A 的子结构
• isSameTree(A *TreeNode, B *TreeNode) bool - 辅助函数：判断两个树是否相同

2. 运行测试

# 运行单元测试
go test -v

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

3. 检查代码格式

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

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

时间和空间复杂度分析

• 时间复杂度： O(MN)，其中 M 是树 A 的节点数，N 是树 B 的节点数
  • 最坏情况下需要遍历 A 的每个节点，对每个节点都要完整匹配一次 B
• 空间复杂度： O(max(M, N))，递归调用栈的深度

知识点

• 二叉树的遍历
• 递归思想的应用
• 双重递归的设计模式
• 树的结构匹配算法
• 边界条件的处理

注意事项

1. 空树处理： 题目约定空树不是任何树的子结构
2. 节点值匹配： 只有节点值相等且结构相同才算匹配
3. 递归终止条件： 正确处理各种边界情况
4. 双重递归： 外层找位置，内层做匹配