树的子结构【Java版】

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

public class Solution {//分两步:
    //[1]遍历root1树，尝试每一个节点
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null)return false;//由题，root1或root2初试为null都会导致false
        if(judge(root1,root2)==true)return true;//必须要有if判断 ==>只有true才返回、并结束题目任务；false时不能返回,并进行下方的详细判别
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);//这里的关系是"或"
    }                                                                          //表示整个树的所有分支只要有一个末端分支满足即可。
    //[2]针对某一节点node，判断是否与root2匹配
    public boolean judge(TreeNode node, TreeNode root2){
        if(root2==null)return true;//在前，因为有：node和root2都为null的情况，root2为空node不为空的情况（本题允许在匹配时，子树比原树下方短）
        if(node==null)return false;//在后，相当与node==null&&root2!=null
        if(node.val != root2.val)return false;//不相等直接结束，否则继续向下详细检查
        return judge(node.left,root2.left) && judge(node.right,root2.right);//"与"的关系，表示子树所有分支全部都要满足。
    }
}
//judge()函数复杂度为O(root2) //root2是B树（子树）
//HasSubtree()由于每个root1树的节点都要试一下，调用次数O(root1)
//==>时间复杂度 O(root1*root2)