# 剑指 Offer 26. 树的子结构

大家好,我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目,依旧给出了非常详细的题解和精美的配图与动画。

# 一、题目描述

输入两棵二叉树 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);

    }
}