题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
package new_offer;
/**
* 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
* 判断2是不是1的子结构
* 此题我有一个没有考虑到的地方：以为只要两个节点相同就可以了
* （节点是引用类型 不可以如此判断 需要将节点所包含的值及节点的子树的各个值进行比较）
* @author Sonya
*
*/
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class N17_HasSubtree {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean r=false;
if(root2==null) return false;
if(root1==null) return false;
if(root1.val==root2.val) {
r=judege1of2(root1,root2);
}//如果有一个节点对应上 就继续判断下面是否都是满足的
else if(root1.left!=null){
r=HasSubtree(root1.left,root2);
}
else {
r= HasSubtree(root1.right,root2);
}
return r;
}
public static boolean judege1of2(TreeNode node1, TreeNode node2) {
if (node2 == null) {
return true;
}
if (node1 == null) {
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val) {
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return judege1of2(node1.left,node2.left) && judege1of2(node1.right,node2.right);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode t1,t2,t3,t4,t5,t6;
t1=new TreeNode(1);t2=new TreeNode(2);t3=new TreeNode(3);
t4=new TreeNode(4);t5=new TreeNode(5);t6=new TreeNode(6);
t1.left=t2;t1.right=t3;
t2.left=t4;t2.right=t5;
t3.left=t3.right=null;
t4.left=t6;t4.right=null;
t5.left=t5.right=null;
t6.left=t6.right=null;
TreeNode s1,s2,s3;
s1=new TreeNode(2);s2=new TreeNode(4);s3=new TreeNode(5);
N17_HasSubtree n17=new N17_HasSubtree();
boolean b1;
b1=n17.HasSubtree(t2, s1);
System.out.println(b1);
}
}