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

1
boolean HasSubtree(TreeNode root1,TreeNode root2)

首先在 A 中找到一个节点，满足这个节点是 B 的 root 节点，在此基础上按照 B 的结构遍历 A，B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
boolean HasSubtree(TreeNode root1,TreeNode root2) {
    boolean result =false;
    if(root1!=null&&root2!=null){
    if(root1.val==root2.val)
        result=isSubtree(root1,root2);
    if(!result)
        result= HasSubtree(root1.left,root2);
    if(!result)
        result= HasSubtree(root1.right,root2);
    }
    return result;
}

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