【剑指offer】树的子结构

题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
1、思路分析
首先要明白子结构的概念，可以理解为B是A的某一部分，但B的根节点在A的哪一部分并不确定，只要A里能包含B即可。仍然是先判断特殊情况，接着判断两者的根节点的值是否相等，即我们要开始寻找“起点”，如果相等，就判断是否是子树结构（封装在新写的isSubTree函数里，递归写法），不是子树结构，flag=false。回到上一步，如果两者的根节点不相等，递归调用HasSubTree，参数分别为root1.left&root2、root1.right&root2，即重新寻找两者的起点。注意新写函数所放的位置。
2、代码

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2 == null) return false;
        if(root1 == null && root2 != null) return false;
        boolean flag = false;
        if(root1.val == root2.val) { // 找到子树的起点
            flag = isSubTree(root1,root2);
        }
        if(!flag) {
            flag = HasSubtree(root1.left,root2);
            if(!flag) {
                flag = HasSubtree(root1.right,root2);
            }
        }
        return flag;
    }
    private boolean isSubTree(TreeNode root1,TreeNode root2) {
            if(root2 == null) return true;
            if(root1 == null && root2 != null) return false;
            if(root1.val==root2.val){
                return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
            }else{
                return false;
            }
    }
}