树的子结构

来源：牛客网 http://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88

题目描述

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

思路：

（1）在树A中查找等于树B根节点的节点R

（2）判断以R为根节点的子树是否包含了树B

其中（1），可用循环或递归的方式遍历树A。我采用了一个Queue用循环的方式层次遍历。

其中（2），递归的判断R的左右节点是否与B的左右节点相同，终止件是到达了A或B叶子节点。

 1 import java.util.*;
 2 /**
 3 public class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7 
 8     public TreeNode(int val) {
 9         this.val = val;
10 
11     }
12 
13 }
14 */
15 public class Solution {
16     // judging root2 is a subtree of root1 or not
17     public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
18         if(root1==null || root2==null) return false;
19         
20         Queue<TreeNode> queue = new LinkedList<TreeNode>();
21         queue.add(root1);
22         TreeNode node;
23         
24         while (!queue.isEmpty()) {
25             node = queue.poll();
26             if (node.left != null) queue.add(node.left);
27             if (node.right != null) queue.add(node.right);
28 
29             if (node.val==root2.val && isSame(node, root2)) 
30                 return true;
31         }
32         return false;
33     }
34 
35     public static boolean isSame(TreeNode t1, TreeNode t2) {
36         if(t2==null) return true;
37         if(t1==null) return false;
38         if(t1.val!=t2.val) return false;
39         return isSame(t1.left,t2.left) && isSame(t1.right,t2.right);
40     }
41 
42 }

cdcd