剑指offer系列15---树的子结构

15【题目】输入两颗二叉树A，B，判断B是不是A的子结构。

【思路】

　　首先判断A头结点与B头结点是否相同，相同再调用doesTree1HaveTree2（）比较A下一个左右结点值与B下一个左右结点值是否相同；
　　　　　　　　　　　　　　　　　　　不相同再继续查找A的下一个结点与B的头结点是否相同；

　　　　　　　　　　　　//A B头结点均相同，调用函数doesTree1HaveTree2（），继续比较A B剩下的结点是否相同

　　　　　　　　　　　　//不相同,比较A下一个做结点与B头结点是否相同

　　　　　　　　　　　　//A左结点与B头结点仍然不相同，比较A右节点与B结点值

 1 package com.exe3.offer;
 2 
 3 /**
 4  * 15【题目】输入两颗二叉树A，B，判断B是不是A的子结构。
 5  * @author WGS
 6  *
 7  */
 8 public class SubTree {
 9     public static class TreeNode{
10         int val;
11         TreeNode left=null;
12         TreeNode right=null;
13         public TreeNode(int n){
14             this.val=n;
15         }
16         
17     }
18     //首先判断A头结点与B头结点是否相同，相同再调用doesTree1HaveTree2（）比较A下一个左右结点值与B下一个左右结点值是否相同；
19      //                             不相同再继续查找A的下一个结点与B的头结点是否相同；
20     public boolean hasSubtree(TreeNode A,TreeNode B){
21         boolean flag=false;
22         if(A!=null && B!=null){
23             //A B头结点均相同，调用函数doesTree1HaveTree2（），继续比较A B剩下的结点是否相同
24             if(A.val==B.val) 
25                 flag=doesTree1HaveTree2(A,B);
26             //不相同,比较A下一个做结点与B头结点是否相同
27             if(!flag)
28                 flag=hasSubtree(A.left,B);
29             //A左结点与B头结点仍然不相同，比较A右节点与B结点值
30             if(!flag)
31                 flag=hasSubtree(A.right,B);
32         }
33         return flag;
34         
35     }
36     //
37     public boolean doesTree1HaveTree2(TreeNode A,TreeNode B){
38         if(B==null)        return true;
39         if(A==null)        return false;
40         if(A.val!=B.val)  return false;//头结点不同的话
41         //头结点相同，再用递归比较A,B中左右结点是否依次相同
42         return doesTree1HaveTree2(A.left,B.left)&&doesTree1HaveTree2(A.right,B.right);
43         
44     }
45     public static void main(String[] args){
46         TreeNode A1=new TreeNode(8);
47         TreeNode A2=new TreeNode(8);
48         TreeNode A3=new TreeNode(7);
49         TreeNode A4=new TreeNode(9);
50         TreeNode A5=new TreeNode(2);
51         TreeNode A6=new TreeNode(4);
52         TreeNode A7=new TreeNode(7);
53         A1.left=A2;
54         A1.right=A3;
55         A2.left=A4;
56         A2.right=A5;
57         A5.left=A6;
58         A5.right=A7;
59         
60         TreeNode B1=new TreeNode(8);
61         TreeNode B2=new TreeNode(9);
62         TreeNode B3=new TreeNode(2);
63         B1.left=B2;
64         B1.right=B3;
65         boolean flag=new SubTree().hasSubtree(A1, B1);
66         System.out.println(flag);
67     }
68 }