24.树的子结构(148)

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

• 代码

  package _24.树的子结构;
  
  /**
   * 题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。
   * （ps：我们约定空树不是任意一个树的子结构）
   * @author Administrator
   *
   */
  public class SubStructureInBTree {
  	public boolean HasSubtree(TreeNode root1, TreeNode root2) {
  		if(root1 == null || root2 == null) return false;
  		boolean flag = false;
  		//如果找到了root1中root2的根结点：以这个根节点为为起点判断是否包含root2
  		if(root1.val == root2.val){
  			 flag = isSubtree(root1,root2);
  		}
  		// 如果找不到，那么就再去root1的左孩子、右孩子当作起点
  		if(!flag){
  			flag = HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
  		}
  		return flag;
  		
  //		return isSubtree(root1, root2) ||
  //				HasSubtree(root1.left,root2) ||
  //				HasSubtree(root1.right,root2);
  	}
  	public static boolean isSubtree(TreeNode root1, TreeNode root2) {
  		//如果root2为空，则表明root2的结点已经对应完
  		if(root2 == null) return true;
  		//如果root1为空，则表明root2的结点还没对应完，但是root1已经没有结点
  		if(root1 == null) return false;
  		if(root1.val != root2.val) return false;
  		//如果根结点对应，则继续往下判断
  		return isSubtree(root1.left,root2.left) && isSubtree(root1.right, root2.right);
  	}
  	
  	public static void main(String[] args) {
  		
  		TreeNode root1 = new TreeNode(8);
  		TreeNode node1 = new TreeNode(8);
  		TreeNode node2 = new TreeNode(7);
  		TreeNode node3 = new TreeNode(9);
  		TreeNode node4 = new TreeNode(2);
  //		TreeNode node5 = new TreeNode(5);
  //		TreeNode node6 = new TreeNode(6);
  		root1.left = node1;
  		root1.right = node2;
  		
  		node1.left = node3;
  		node1.right = node4;
  //		node3.left = node5;
  //		node3.right = node6;
  		
  		TreeNode root2 = new TreeNode(8);
  		TreeNode node7 = new TreeNode(9);
  		TreeNode node8 = new TreeNode(2);
  		
  		root2.left = node7;
  		root2.right = node8;
  		SubStructureInBTree tree = new SubStructureInBTree();
  		boolean hasSubtree = tree.HasSubtree(root1, root2);
  		System.out.println(hasSubtree);
  	}
  }
  class TreeNode {
      int val = 0;
      TreeNode left = null;
      TreeNode right = null;
  
      public TreeNode(int val) {
          this.val = val;
      }
  }