java-树的子结构

题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例1
输入
{8,8,#,9,#,2,#,5},{8,9,#,2}
返回值
true

解题思路
参考https://blog.csdn.net/qinian_ztc/article/details/104731375
首先确定什么是子结构-就是是原来树的一部分就行，没有必要就是一颗子树
如图为一对子树结构

那么思路大概如下
先在A树中找到和B树根节点一样的节点，之后判断左右子树是否相等。假如B树没了，A树还有是可以的。反之不行
需要从A树的根节点依次遍历直到找到

可以归纳为-取之参考博客
1.在大树中找到和小树根节点相同的节点。
2.然后以此节点为根节点，在大树上往下搜索对比小书左右节点是否相同，不同则返回false
3.如果2步中最后返回false 回到第一步，从大树的左子树找和小树根节点相同的节点。
4.如果3步中最后返回false 回到第一步，从大树的右子树找和小树根节点相同的节点。

java代码

/**
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;
        boolean ans=false;
        if(root1.val==root2.val){
            ans=Subtree(root1,root2);
        }
        if(!ans) ans=HasSubtree(root1.left,root2);
        if(!ans) ans=HasSubtree(root1.right,root2);
        return ans;
    }
    public boolean Subtree(TreeNode root1,TreeNode root2){
        if(root2==null) return true;
        if(root1==null) return false;
        if(root1.val != root2.val) return false;
        return Subtree(root1.left,root2.left) && Subtree(root1.right,root2.right);
    }
}