剑指 Offer 26. 树的子结构
题目
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
1 |
|
给定的树 B:
1
2
3 4
/
1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
1 |
|
示例 2:
1 |
|
题解
思路
若树B是树A的子结构,则子结构的根节点可能为树A的任意一个节点。因此,判断树B是否是
树A的子结构,需完成以下两步工作:
- 先序遍历树A中的每个节点na ; (对应函数 isSubStructure(A, B) )
- 判断树A中以nA为根节点的子树是否包含树B。(对应函数 recur(A, B) )
算法流程:
1 |
|
recur(A, B)函数: .
- 终止条件:
- 当节点B为空:说明树B已匹配完成(越过叶子节点),因此返回true ;
- 当节点A为空:说明已经越过树A叶子节点,即匹配失败,返回false ;
- 当节点A和B的值不同:说明匹配失败,返回false ;
- 返回值:
- 判断A和B的左子节点是否相等,即
recur(A. left,B. left) ; - 判断A和B的右子节点是否相等,即recur (A. right, B. right) ;
- 判断A和B的左子节点是否相等,即
isSubStructure(A, B)函数:
- 特例处理:当树A为空或树B为空时,直接返回false;
- 返回值:若树B是树A的子结构,则必满足以下三种情况之一, 因此用或||连接;
- 以节点A为根节点的子树包含树B,对应recur(A,B);
- 树B是树A左子树的子结构,对应isSubStructure(A. left, B) ;
- 树B是树A石子树的子结构,对应i sSubStructure(A. right,B) ;
以上2.3. 实质上是在对树A做先序遍历。
代码
1 |
|
剑指 Offer 26. 树的子结构
http://lhystutest.top/2023/02/13/算法/剑指offer/剑指 Offer 26. 树的子结构/