大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 26. 树的子结构。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
输入两棵二叉树 A 和 B ，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构， 即 A 中有出现和 B 相同的结构和节点值。
例如:
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
- 0 <= 节点个数 <= 10000
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
要判断 B 是否是 A 的子结构，那么一开始先从 A 和 B 的 根节点 开始。
3 和 4 不相同，说明此时 B 不是 A 根节点的子结构，接下来需要判断 B 是否是 A 的左子树或者右子树的子结构。
A 的左子树的节点值为 4，与 B 的根节点值 4 相同，此时 B 有可能是 A 左子树的子结构，去判断它们各自的左右子节点是否相同。
匹配结果是 B 与 A 的一个子树拥有相同的结构和节点值。
2、规律
二叉树具备天然的递归性，B 与 A 根节点的比较、 B 与 A 左右子树的比较、B 左右子节点与 A 左右子树的子节点的比较代码是一样。
3、匹配
递归。
4、边界
- 若 A 为空，返回 false 。
- 若 B 为空，返回 false 。
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 一开始如果 A 或者 B 为空，直接返回 false
// 因为题目约定空树不是任意一个树的子结构
if( A == null || B == null){
return false;
}
// 接下来去以下几种情况
// A 的根节点 VS B 的根节点（ A 的左右子树的节点 VS B 的根节点）
// 1、A 的根节点和 B 的根节点相同情况，依次比较它们的子节点
// 2、A 的根节点和 B 的根节点不相同情况， A 的左子树 VS B 的根节点
// 3、A 的根节点和 B 的根节点不相同情况， A 的右子树 VS B 的根节点
return isSub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
}
boolean isSub(TreeNode A, TreeNode B){
// A 和 B 不匹配的情况有很多，我们需要一开始去找它们完全匹配的情况
// 即遍历完 B ，直到为 null，说明 B 的全部节点都和 A 的子结构匹配上
if( B == null ){
return true;
}
// A 中的节点为空，但 B 中的节点不为空，说明不匹配
if( A == null ){
return false;
}
// A 和 B 都不为空 ，但数值不同，说明不匹配
if( A.val != B.val){
return false;
}
// 此时，当前这个点是匹配的，继续递归判断左子树和右子树是否「分别匹配」
return isSub(A.left, B.left) && isSub(A.right, B.right);
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(MN)。 其中 M 和 N 分别为树 A和 树 B 的节点数量。
空间复杂度
空间复杂度为 O(M)。
七、相关标签
- 二叉树
- 递归
