剑指Offer第十七题：树的子结构

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

解答：
1.子结构相同指的是能在待匹配的树中找到一个相同形状和数值的树。这里和子树相同有些不一样。

public class Q_17 {

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root2==null){
        return false;
    }
    return HasSubtree1(root1,root2);
}
public boolean HasSubtree1(TreeNode root1,TreeNode root2) {
    if(root1!=null){
        return Comparetree(root1, root2)||HasSubtree1(root1.left, root2)
                ||HasSubtree1(root1.right, root2);
    }
    return false;
}
//判断root2是否root1的一部分（ps 从根节点起开始比较）
public boolean Comparetree(TreeNode root1,TreeNode root2){
    if(root2==null){//如果匹配树的节点为null值，表明已经完全匹配，返回true
        return true;
    }
    if(root1==null&&root2!=null){//如果待匹配树的节点为null值，表明不匹配，返回false
        return false;
    }
    if(root1.val!=root2.val){
        return false;
    }else{
        return Comparetree(root1.left, root2.left)&&Comparetree(root1.right, root2.right);
    }
}
public static void main(String[] args) {
    TreeNode node_8_1=new TreeNode(8);
    TreeNode node_8_1_1=new TreeNode(8);
    TreeNode node_7_1=new TreeNode(7);
    TreeNode node_9_1=new TreeNode(9);
    TreeNode node_2_1=new TreeNode(2);

    node_8_1.left=node_8_1_1;
    node_8_1.right=node_7_1;
    node_8_1_1.left=node_9_1;
    node_8_1_1.right=node_2_1;

    TreeNode node_8=new TreeNode(8);
    TreeNode node_9=new TreeNode(9);
    TreeNode node_2=new TreeNode(2);
    node_8.left=node_9;
    node_8.right=node_2;
    System.out.println(new Q_17().HasSubtree(node_8_1, node_8));
}

}