剑指offer 17. 树的子结构 | 力扣 572. 另一棵树的子树

子树的意思是包含了一个结点，就得包含这个结点下的所有节点，一棵大小为n的二叉树有n个子树，就是分别以每个结点为根的子树。

子结构的意思是包含了一个结点，可以只取左子树或者右子树，或者都不取。

代码实现只有一行代码不同

17. 树的子结构

题目描述

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

思考：

一个树是另一个树的子结构则

要么这个树是另一棵树的同根的子结构
要么这个树是左树的子结构
要么这个树是右树的子结构

 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 }

力扣 572. 另一棵树的子树

另一棵树的子树

一个树是另一个树的子树则

要么这两个树相等
要么这个树是左树的子树
要么这个树hi右树的子树

 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 }