前言
牛客网剑指offer的66道题，刷起来！每道题会提供简单的思路以及测试通过的代码
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。(ps：我们约定空树不是任意一个树的子结构)
二叉树结构：
1 class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6 }
注：点击左下角的阅读原文即可跳转到原文，可以提交代码
解答思路
对于与二叉树有关的题目，90% 是采取递归的方式来解决比较简单的，这道题也是。
首先我们先以 A 的根节点 root1 作为起点来判断 B 是否为 A的子结构。 如果是则直接返回 true，如果不是，则递归以 root1.left 和 root1.right 作为起点来判断。代码如下：
1public class 树的子结构 {
2 public boolean HasSubtree(TreeNode root1,TreeNode root2) {
3 if (root2 == null || root1 == null) {
4 return false;
5 }
6 // 判断 B 是否为 A 的子结构
7 return isSubTree(root1, root2);
8 }
9
10 // 判断 B 是否为 A 的子结构
11 private boolean isSubTree(TreeNode root1, TreeNode root2) {
12 if (root1 == null) {
13 return false;
14 }// 以root1为root2的根节点，判断子结构是否成立
15 if (judge(root1, root2)) {
16 return true;
17 } else {
18 // 如果root1作为起点不行，则递归判断左右节点
19 return isSubTree(root1.left, root2) || isSubTree(root1.right, root2);
20 }
21 }
22 // 以root1为root2的根节点，判断子结构是否成立
23 private boolean judge(TreeNode root1, TreeNode root2) {
24 if(root2 == null)
25 return true;
26 if(root1 == null)
27 return false;
28 if(root1.val == root2.val)
29 return judge(root1.left, root2.left) && judge(root1.right, root2.right);
30
31 return false;
32 }
33}
往期
剑指offer：重建二叉树
剑指offer：二进制中1的个数
剑指offer：数值的整次数方
剑指offer：二维数组中的查找
关注我 ，每天进步一点点