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 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);
	}
}

评论

2 楼 bylijinnan 2012-06-19  

neyshule 写道

tree1HaveAllNodesOfTree2这个函数为什么这样写呢：
        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()); 
为什么tree2是null就是true？tree1是null是false?

tree1HaveAllNodesOfTree2这个方法是判断是否tree1包含了tree2的所有节点，如果tree2是空树，那就认为tree1包含了tree2，反之则不是

这方法是在递归里面调用的，会有一个时候出现tee1==null 或者tree2==null

1 楼 neyshule 2012-06-19  

tree1HaveAllNodesOfTree2这个函数为什么这样写呢：
        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()); 
为什么tree2是null就是true？tree1是null是false?