剑指offer -- 树的子结构

解法

一个树是不是另外的树的子结构 只有三种情况
第一种就是 根相等，第二种是 和左子树中的某一部分相等，第三种是和右子树的某一部分相等。
假设 我们遇到的情况是 根相等的情况，我们就到了root2是不是和root1相等的情况，递归遍历的情况 只有root2遍历到了null 就说明相等，其他情况 比如 root1先到null，或者val不相等 都是说明不是子树的情况。
然后我们只需要符合三种情况中的一种 就可以得出是不是子结构了。

代码

/**
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(root2 == null || root1 == null){ // 根据约定 空树 不是任意树的子结构
            return false;
        }
        // 第一个条件是 根相等 第二个条件是 root2 是root1左子树的子结构 第三个条件是 root2 是root1右子树的 子结构
        return isSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    public boolean isSubTree(TreeNode root1,TreeNode root2){
        if(root2 == null){ //root2 遍历完了 说明是相等的情况
            return true;
        }
        if(root1==null || root1.val != root2.val){ // root1 提前结束 或者值不相等 都说明不是相等的情况
            return false;
        }
        // 这里是 左右子树比较。
        return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
    }
}