# java-50-输入两棵二叉树A和B，判断树B是不是A的子结构

```import ljn.help.*;
public class HasSubtree {

/**Q50.
* 输入两棵二叉树A和B，判断树B是不是A的子结构。

1                                                     8
/   \                                                 /    \
8     7                                                9    2
/    \
9     2
/  \
4    7
*/
public static void main(String[] args) {
int[] data01={1,8,7,9,2,0,0,0,0,4,7};
Node tree01=Helper.createTree(data01);
int[] data02={8,9,2};
Node tree02=Helper.createTree(data02);

boolean result=hasSubtree(tree01,tree02);
System.out.println(result);//true

/*
* hasSubtreeByOrder() does not work.
* preOrder and inOrder can define a unique BTree,but
* inOrderOfTree1=9,8,4,2,7,1,7
* inOrderOfTree2=9,8,2
*/
result=hasSubtreeByOrder(tree01,tree02);
System.out.println(result);//false

}

//hasSubtree():just some "boundary condition".see hasSubtreeCore().
public static boolean hasSubtree(Node tree1,Node tree2){
if((tree1==null&&tree2!=null)||
tree1!=null&&tree2==null){
return false;
}
if(tree1==null&&tree2==null){
return true;
}
return hasSubtreeCore(tree1,tree2);
}

public static boolean hasSubtreeCore(Node tree1,Node tree2){
boolean result=false;
if(tree1.getData()==tree2.getData()){//if roots are equal,test if both leftTree and rightTree are equal
result=tree1HaveAllNodesOfTree2(tree1,tree2);
}
//roots are not equal
if(!result&&tree1.getLeft()!=null){//find tree2 in tree1's left child,if exists
result=hasSubtreeCore(tree1.getLeft(),tree2);
}
if(!result&&tree1.getRight()!=null){//find tree2 in tree1's right child,if exists
result=hasSubtreeCore(tree1.getRight(),tree2);
}
return result;
}

public static boolean tree1HaveAllNodesOfTree2(Node tree1,Node tree2){
if(tree2==null){
return true;
}
if(tree1==null){
return false;
}
if(tree1.getData()!=tree2.getData()){
return false;
}
//now the roots are equal.Test left tree and right tree
return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
}

public static boolean hasSubtreeByOrder(Node tree1,Node tree2){
StringBuilder sb=new StringBuilder();
preOrder(tree1,sb);
String preOrderOfTree1=sb.toString();

sb.setLength(0);

preOrder(tree2,sb);
String preOrderOfTree2=sb.toString();
if(preOrderOfTree1.indexOf(preOrderOfTree2)==-1){
return false;
}

sb.setLength(0);
inOrder(tree1,sb);
String inOrderOfTree1=sb.toString();

sb.setLength(0);
inOrder(tree2,sb);
String inOrderOfTree2=sb.toString();

return inOrderOfTree1.indexOf(inOrderOfTree2)!=-1;
}
public static void preOrder(Node node,StringBuilder sb){
if(node==null){
return;
}
sb.append(node.getData()+",");
preOrder(node.getLeft(),sb);
preOrder(node.getRight(),sb);
}
public static void inOrder(Node node,StringBuilder sb){
if(node==null){
return;
}
inOrder(node.getLeft(),sb);
sb.append(node.getData()+",");
inOrder(node.getRight(),sb);
}
}

```

java-50-输入两棵二叉树A和B，判断树B是不是A的子结构

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊