剑指offer 树的子结构

题目详情

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路

1. 当root1 与 root2 相等

      从 该节点 开始往下 循环判断 
   ``` 
   2. 当root1 与 root2 不相等

   root1的left节点 与 root2 循环判断

   <!-- more -->
   
   3. 循环判断

   a. 若 root2 == null ,表示子树已经遍历完毕,返回true

   b. 若 root1 == null , 表示 root2 还没遍历完，root1已经遍历完,不匹配返回false

   c. 若 root1 != root2,不匹配返回false

   d. 若 root1 == root2

   则 往下判断 root1.left == root2.left 和 root1.right == root2.right

### 代码

/**
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) {
boolean res = false;
if(root1!=null && root2!=null){
//如果相等则进入查找循环
if(root1.val == root2.val){
res = isSubTree(root1,root2);
}
//不相等则往子树进行判断
if(!res){
res = HasSubtree(root1.left,root2);
}
//右子树进行判断
if(!res){
res = HasSubtree(root1.right,root2);
}

    }
    return res;
}

public boolean isSubTree(TreeNode root1, TreeNode root2){
    if(root2 == null){
        return true;
    }
    if(root1 == null){
        return false;
    }
    if(root1.val != root2.val){
        return false;
    }else{
        return (isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right));
    }

}

}
```