- 先对比根节点
- 根节点相同递归对比左节点与右节点
- 当B访问到为空则说明 为子结构
- 当A访问为空 说明B不为子结构
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
//先比较根节点的值
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null || root2==null){
return false; //遍历到 两个节点都为空
}
if(isSubtree(root1,root2)) //递归判断节点值
{
return true; //全部相等
}else{
return HasSubtree(root1.left,root2)|| HasSubtree(root1.right,root2);//不相等
}
}
public boolean isSubtree(TreeNode treeA,TreeNode treeB){
if(treeB==null){
return true; //B全部对比完成
}
if(treeA==null){
return false; //A全部对比完成但是B没有对比完成
}
if(treeB.val==treeA.val){
//当 根节点相同开始对比左节点 在对比右节点
return isSubtree(treeA.left,treeB.left) && isSubtree(treeA.right,treeB.right);
}else{
return false;
}
}
}