子树判断问题（百度笔试题）

问题描述：给定两个二叉树的根节点，判断第二树是否是第一个树的子树，如果是返回1，否则返回0.

分析：这个是百度的一道笔试题目，属于经典的数据结构问题，子树判断问题，针对这个问题可以采用递归的方法判断，

拿第二个树的每个节点去和第一个树做匹配，如果某个节点匹配成功，就接着往下匹配，否则重新从第二个树的的根节点开始。

针对这个问题，我写出了一个Java接口类供读者参考，读者直接调用即可。具体代码如下：

 1 public class SubBinaryTree {
 2 
 3     public static int isSubTree(TNode root1,TNode root2){          
 4         int f=0;
 5         boolean r=isPartTree(root1, root2);
 6         if(r==false)f=-1;                                     //非子树返回-1
 7         else {
 8             f=1;                                          //子树返回1
 9         }
10         return f;
11     }
12     public static boolean isPartTree(TNode root1,TNode root2){
13         boolean f=false;
14         if(root1!=null&&root2!=null){
15             if(root1.value==root2.value)                  //判断根节点
16                 f=isPart(root1, root2);
17             if(!f)
18                 f=isPartTree(root1.left, root2);      //判断左匹配
19             if(!f)
20                 f=isPartTree(root1.right, root2);     //判断右匹配
21         }
22         
23         return f;
24     }
25     
26     public static boolean isPart(TNode root1,TNode root2){        //递归判断调用
27         if(root2==null)
28             return true;
29         if(root1==null)
30             return false;
31         if(root1.value!=root2.value)
32             return false;
33         return isPart(root1.left, root2.left)&&isPart(root1.right, root2.right);
34     }
35 }