大家好,我是程序员吴师兄,欢迎来到 图解剑指 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 。

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 26. 树的子结构.002

剑指 Offer 26. 树的子结构.003

剑指 Offer 26. 树的子结构.004

剑指 Offer 26. 树的子结构.005

剑指 Offer 26. 树的子结构.006

剑指 Offer 26. 树的子结构.007

五、参考代码

// 登录 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)。 其中 MN 分别为树 A和 树 B 的节点数量。

空间复杂度

空间复杂度为 O(M)。

七、相关标签

  • 二叉树
  • 递归

发表评论

邮箱地址不会被公开。 必填项已用*标注