剑指offer 17. 树的子结构

 1 public class Solution {
 2     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 3        // 排序特殊情况
 4         if(root2 == null || root1 == null)
 5             return false;
 6         // 判断 root2 是否为 与 root1 同根的子结构，如果不是判断是否是其左右子树的子结构
 7         return judgeSubtree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
 8     }
 9     
10     // 判断 root2 是否为 root1 同根的子结构
11     public boolean judgeSubtree(TreeNode root1, TreeNode root2){
12         // 只要root2 到达叶子结点即返回true
13         if(root2 == null)
14             return true;
15         // 如果 root1 先到达叶子结点返回 false
16         if(root1 == null)
17             return false;
18         // 如果两个结点值不相等，直接返回 false
19         if(root1.val != root2.val)
20             return false;
21         
22         // 判断左右子树是否相等
23         return judgeSubtree(root1.left, root2.left) && judgeSubtree(root1.right, root2.right);
24     }
25     
26     
27 }

 1 class Solution {
 2     public boolean isSubtree(TreeNode s, TreeNode t) {
 3         if(s == null || t == null)
 4         return false;
 5 
 6         return judgeSubtree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
 7             
 8     }
 9     public boolean judgeSubtree(TreeNode root1, TreeNode root2){
10         // 两个树必须同时到达叶子结点才返回 true
11         if(root1 == null && root2 == null)　　　　　　　　// 唯一不同的地方
12             return true;
13         if(root1 == null || root2 == null){
14             return false;
15         }
16         // 如果结点值不相等，返回 false
17         if(root1.val != root2.val)
18             return false;
19         return judgeSubtree(root1.left, root2.left) && judgeSubtree(root1.right, root2.right);
20 
21     }
22 }