输入两棵二叉树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
- 首先这里不确定的就是,如果结果为 true,那么 A 中哪个节点为 B 的头结点。既然不确定,那么就遍历树 A,然后判断每个节点是否就是 B 的头结点,或者说以 A 此时节点为头结点是否包含 B。
- 判断 B 是否为给定头节点的树的子树,那么只需要递归判断每个节点即可。当 B 结点为 null 说明比较完了都没啥问题,那自然返回 true,而如果 A 都被比较完了 B 还有剩下的节点还没判断,那肯定返回 false,或者 A B 此时的结点的值不同,那也返回 false,否则继续比较左右节点。
-
// 递归遍历树 A public boolean isSubStructure(TreeNode A, TreeNode B) { return (A!=null && B!=null) && ( dfs(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B) ); } public boolean dfs(TreeNode A,TreeNode B){ if(B == null)return true; if(A == null || A.val != B.val)return false; return dfs(A.left,B.left) && dfs(A.right,B.right); }