剑指 Offer 26. 树的子结构
一、题目描述
输入两棵二叉树 A 和 B ，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构， 即 A 中有出现和B相同的结构和节点值。
二、题目解析
要判断 B 是否是 A 的子结构，那么一开始先从 A 和 B 的 根节点 开始。
3 和 4 不相同，说明此时 B 不是 A 根节点的子结构，接下来需要判断 B 是否是 A 的左子树或者右子树的子结构。
A 的左子树的节点值为 4，与 B 的根节点值 4 相同，此时 B 有可能是 A 左子树的子结构，去判断它们各自的左右子节点是否相同。
匹配结果是 B 与 A 的一个子树拥有相同的结构和节点值。
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
三、参考代码
// 登录 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);
}
}
