【数据结构-二叉树 九】【树的子结构】:树的子结构

这篇具有很好参考价值的文章主要介绍了【数据结构-二叉树 九】【树的子结构】:树的子结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【子结构】,使用【二叉树】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。

【数据结构-二叉树 九】【树的子结构】:树的子结构,# 二叉树,数据结构

明确目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍

树的子结构【MID】

双重递归,前所未有的体验

题干

直接粘题干和用例【数据结构-二叉树 九】【树的子结构】:树的子结构,# 二叉树,数据结构
【数据结构-二叉树 九】【树的子结构】:树的子结构,# 二叉树,数据结构

解题思路

原题解地址,若树 B 是树 A 的子结构,则子结构的根节点可能为树 A 的任意一个节点。因此,判断树 B 是否是树 A 的子结构,需完成以下两步工作:

  1. 先序遍历树 A 中的每个节点 node ;(对应函数 isSubStructure(A, B)
  2. 判断树 A 中以 node 为根节点的子树是否包含树 B 。(对应函数 recur(A, B)

【数据结构-二叉树 九】【树的子结构】:树的子结构,# 二叉树,数据结构
树 A 的根节点记作 节点 A ,树 B 的根节点称为 节点 B

recur(A, B) 函数

终止条件:

  • 当节点 B 为空:说明树 B 已匹配完成(越过叶子节点),因此返回 true ;
  • 当节点 A 为空:说明已经越过树 A 的叶节点,即匹配失败,返回 false;
  • 当节点 A 和 B 的值不同:说明匹配失败,返回 false ;

返回值:

  • 判断 A 和 B 的 左子节点 是否相等,即 recur(A.left, B.left)
  • 判断 A 和 B 的 右子节点 是否相等,即 recur(A.right, B.right)

isSubStructure(A, B) 函数

特例处理: 当 树 A 为空 或 树 B 为空 时,直接返回 false;

返回值: 若树 B 是树 A 的子结构,则必满足以下三种情况之一,因此用或 || 连接;

  • 以 节点 A 为根节点的子树 包含树 B ,对应 recur(A, B);
  • 树 B 是 树 A 左子树 的子结构,对应 isSubStructure(A.left, B)
  • 树 B 是 树 A 右子树 的子结构,对应 isSubStructure(A.right, B)

【数据结构-二叉树 九】【树的子结构】:树的子结构,# 二叉树,数据结构

代码实现

给出代码实现基本档案

基本数据结构二叉树
辅助数据结构
算法递归
技巧

其中数据结构、算法和技巧分别来自:

  • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
  • 技巧:双指针、滑动窗口、中心扩散

当然包括但不限于以上文章来源地址https://www.toymoban.com/news/detail-727681.html

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 1 如果A树或B树为空,则匹配失败
        if (A == null || B == null) {
            return false;
        }
        // 2 A的当前节点包含B,或A的左子树包含B,或A的右子树包含B
        return isNodeSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean isNodeSub(TreeNode node, TreeNode B) {

        // 1 如果B为空,说明B节点比对完成,匹配成功【终止条件】
        if (B == null ) {
            return true;
        }

        // 2 如果B不为null,且node为空,说明尚未匹配完B但已越过A的节点树叶子节点,匹配失败【终止条件】
        if (node == null ) {
            return false;
        }

        // 3 如果node节点值不等于B,则说明不是子结构,匹配失败【本层任务】
        if (node.val != B.val) {
            return false;
        }

        // 4 比较node与B的左右子节点,必须都满足条件才可以【返回值】
        return isNodeSub(node.left, B.left) && isNodeSub(node.right, B.right);
    }
}

复杂度分析

  • 时间复杂度 O(MN): 其中 M,N分别为树 A 和 树 B 的节点数量;先序遍历树 A 占用 O(M) ,每次调用 recur(A, B) 判断占用 O(N)。
  • 空间复杂度 O(M) : 当树 A 和树 B 都退化为链表时,递归调用的深度取决于二叉树A的高度,最坏情况下,二叉树A是一个完全不平衡的树,高度为M,因此递归调用的最大深度为M。每次递归调用都需要一些额外的栈空间来保存函数调用的上下文,因此空间复杂度为O(M)

到了这里,关于【数据结构-二叉树 九】【树的子结构】:树的子结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(48)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(57)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(59)
  • 【数据结构】二叉树的介绍和二叉树堆

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        树这一概念,在我们刚开始听说的时候会觉得

    2024年01月20日
    浏览(52)
  • 【数据结构】树,二叉树,满二叉树,完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(70)
  • 【数据结构】二叉树的顺序结构-堆

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而 完全二叉树 更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个

    2024年02月09日
    浏览(53)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(59)
  • 【数据结构】二叉树的概念及结构

    🚀write in front🚀 📜所属专栏: 初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!! 树是一种 非线性的数据结构

    2023年04月23日
    浏览(44)
  • 数据结构:二叉树的顺序结构--堆

    朋友们、伙计们,我们又见面了,本期来给大家解读一下二叉树--堆的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 目录 前言: 1.堆的概念及

    2024年02月06日
    浏览(47)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包