剑指 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);

    }
}