算法1
二叉树(递归)
代码分两个方法
1、判断当前A树的当前节点和B树的根节点是否相同
2、如果相同,判断其他位置是否相同
第一个方法,直接遍历A树即可
第二个方法,
-
如果B树的节点为空,则证明A的节点和B的所有节点都相同了,所以直接返回true
-
如果B树节点不为空,A树节点为空,则说明不匹配
-
如果两个节点的值不同,则不匹配
-
如果当前位置匹配,递归AB两棵树各自的左子树和右子树是否匹配
Java 代码
class Solution {
public boolean hasSubtree(TreeNode root1, TreeNode root2) {
boolean res=false;
if(root1!=null && root2!=null){
if(root1.val == root2.val){
res = helpHasSubtree(root1,root2);
}
if(!res){
res = hasSubtree(root1.left,root2);
}
if(!res){
res = hasSubtree(root1.right,root2);
}
}
return res;
}
public boolean helpHasSubtree(TreeNode root1, TreeNode root2){
if(root2==null)
return true;
if(root1==null)
return false;
if(root1.val!=root2.val)
return false;
return helpHasSubtree(root1.left,root2.left)&&helpHasSubtree(root1.right,root2.right);
}
}