LeetCode 剑指 Offer 26. 树的子结构

题目描述

✅ 剑指 Offer 26. 树的子结构

image-20241107205339686

image-20250418234136559

思路分析

思路描述

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



// 判断 B 是否是从 A 开始的子结构
func match(A, B *TreeNode) bool {
	if B == nil {
		return true // B 匹配完了
	}
	if A == nil || A.Val != B.Val {
		return false
	}
	return match(A.Left, B.Left) && match(A.Right, B.Right)
}

// 判断 B 是否为 A 的子结构
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}
	return match(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

  • 时间复杂度：O (m * n)，其中 m 是树 A 的节点数，n 是树 B 的节点数。

    最坏情况下需要遍历 A 的每个节点，并且在每个节点上都需要遍历 B。

  • 空间复杂度：O (h)，其中 h 是树 A 的高度，递归调用栈的空间复杂度。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/85666181
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！