题目描述:
给定两棵二叉树 tree1
和 tree2
,判断 tree2
是否以 tree1
的某个节点为根的子树具有 相同的结构和节点值 。
注意,空树 不会是以 tree1
的某个节点为根的子树具有 相同的结构和节点值 。
示例 1:
输入:tree1 = [1,7,5], tree2 = [6,1] 输出:false 解释:tree2 与 tree1 的一个子树没有相同的结构和节点值。
示例 2:
输入:tree1 = [3,6,7,1,8], tree2 = [6,1] 输出:true 解释:tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。
提示:
0 <= 节点个数 <= 10000
代码:
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null)
return false;
//先从根节点判断B是不是A的子结构,如果不是在分别从左右两个子树判断,
//只要有一个为true,就说明B是A的子结构
return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
boolean isSub(TreeNode A, TreeNode B) {
//这里如果B为空,说明B已经访问完了,确定是A的子结构
if (B == null)
return true;
//如果B不为空A为空,或者这两个节点值不同,说明B树不是
//A的子结构,直接返回false
if (A == null || A.val != B.val)
return false;
//当前节点比较完之后还要继续判断左右子节点
return isSub(A.left, B.left) && isSub(A.right, B.right);
}