1 // 遍历整个树
2 public boolean HasSubtree(TreeNode root1, TreeNode root2) {
3 boolean result = false;
4 // 如果root1,root2中只要有一个是null,则返回false
5 if (root1 != null && root2 != null) {
6 // 找到两个数值相同的根节点
7 if (root1.val == root2.val) {
8 // 判断以这个根节点的子树，是否包含root2
9 result = doesTree1HasTree2(root1, root2);
10 }
11 // 如果不包含，则继续到root1的左边去查找与root2根结点相同的节点
12 if (!result) {
13 result = HasSubtree(root1.left, root2);
14 }
15 // 如果不包含，则继续到root1的右边去查找与root2根结点相同的节点
16 if (!result) {
17 result = HasSubtree(root1.right, root2);
18 }
19 }
20 return result;
21 }
22
23 public boolean doesTree1HasTree2(TreeNode root1, TreeNode root2) {
24 // 如果子树为空，则返回true
25 if (root2 == null) {
26 return true;
27 }
28 // 走到这里，说明root2不为空，而如果roo1为空，则返回false
29 if (root1 == null) {
30 return false;
31 }
32 // 走到这里，说明root1，root2均不为空，判断它们的值是否相等
33 if (root1.val != root2.val) {
34 return false;
35 }
36 // 如果root1的值=root2的值，则递归判断root1的左边和root2的做左边
37 // 如果root1的值=root2的值，则递归判断root1的右边和root2的做右边
38 return doesTree1HasTree2(root1.left, root2.left) &&
39 doesTree1HasTree2(root1.right, root2.right);
40 }