剑指 Offer 26. 树的子结构 #
- 标签:树、深度优先搜索、二叉树
- 难度:中等
题目大意 #
给定两棵二叉树的根节点 A
、B
。
要求:判断 B
是不是 A
的子结构。(空树不是任意一棵树的子结构)。
B
是A
的子结构:A
中有出现和B
相同的结构和节点值。
解题思路 #
深度优先搜索。
- 先判断特例,如果
A
、B
都为空树,则直接返回False
。 - 然后递归判断
A
、B
是否相等。- 如果
A
、B
相等,则返回True
。 - 如果
A
、B
不相等,则递归判断B
是否是A
的左子树的子结构,或者B
是否是A
的右子树的子结构,如果有一种满足,则返回True
,如果都不满足,则返回False
。
- 如果
递归判断 A
、B
是否相等的具体方法如下:
- 如果
B
为空树,则直接返回False
,因为空树不是任意一棵树的子结构。 - 如果
A
为空树或者A
节点的值不等于B
节点的值,则返回False
。 - 如果
A
、B
都不为空,且节点值相同,则递归判断A
的左子树和B
的左子树是否相等,判断A
的右子树和B
的右子树是否相等。如果都相等,则返回True
,否则返回False
。
代码 #
|
|