java-50-输入两棵二叉树A和B，判断树B是不是A的子结构
思路来自：http://zhedahht.blog.163.com/blog/static/25411174201011445550396/
import ljn.help.*;public class HasSubtree {/**Q50. * 输入两棵二叉树A和B，判断树B是不是A的子结构。例如，下图中的两棵树A和B，由于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 equalresult=tree1HaveAllNodesOfTree2(tree1,tree2);}//roots are not equalif(!result&&tree1.getLeft()!=null){//find tree2 in tree1's left child,if existsresult=hasSubtreeCore(tree1.getLeft(),tree2);}if(!result&&tree1.getRight()!=null){//find tree2 in tree1's right child,if existsresult=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 treereturn 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);}} 1 楼 neyshule 2012-06-19 tree1HaveAllNodesOfTree2这个函数为什么这样写呢：