专栏首页码上积木LeetCode题解—树的子结构

LeetCode题解—树的子结构

前言

今天继续说说树结构的算法题——树的子结构

题目

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

     3
    / \
   4   5
  / \
 1   2

给定的树 B:

   4 
  /
 1

返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:输入:A = [1,2,3], B = [3,1] 输出:false

示例 2:输入:A = [3,4,5,1,2], B = [4,1] 输出:true

题解

首先,我们能肯定的是会用到遍历,因为要遍历每个节点进行比较。

那就先假设树B就是树A的子结构,而且是从根节点开始比较的,那么我们就可以进行先序遍历,从根节点开始,每个节点进行比较。

先序遍历(Pre-order),按照根左右的顺序沿一定路径经过路径上所有的结点。

比如这样的结构:

//?A
     3
    / \
   4   5
  / \
 1   2

//?B
   3 
  /
 4
  • 首先从根节点开始比较,如果值一样,则比较左节点,右节点。
  • 当树B的某个节点为null,则无须比较,直接返回。
  • 当B的某个节点不为null,则比较和A的相同节点是否一样值,如果值一样则返回true,否则返回false。

根据上述逻辑,我们可以写出遍历方法:

boolean recur(TreeNode A, TreeNode B) {
 //当B某个节点为null,则无需比较了,直接返回true,比较其他节点
    if (B == null)
        return true;
    //如果相同位置的两个节点不相同,则返回false,不用再继续比较了
    if (A == null || A.val != B.val)
        return false;
    //继续往下遍历比较
    return recur(A.left, B.left) && recur(A.right, B.right);
}

这样从根节点开始比较的话,就能找出B是否为子结构。

但是,B不一定从A的根节点开始比较,比如这样的情况:

//?A
     3
    / \
   4   5
  / \
 1   2

//?B
   4 
  /
 1

这种情况肯定就不能直接调用上述的recur方法了,因为根节点就不相同。所以我们需要去把每个节点都进行遍历比较,只要有一个节点及子节点符合条件,就代表B为子结构。

也就是每个节点都要执行上述的recur方法。

public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null)
        return false;
    return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

上述就是用到先序遍历,将A的每个节点都和B比较,然后用或的方式,只要满足一个子节点结构和B相同即可。

最后贴一下完整的代码:

//遍历A的每一个节点
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null)
        return false;
    return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

//同时遍历A和B的相同位置节点
boolean recur(TreeNode A, TreeNode B) {
 //当B某个节点为null,则无需比较了,直接返回true,比较其他节点
    if (B == null)
        return true;
    //如果相同位置的两个节点不相同,则返回false,不用再继续比较了
    if (A == null || A.val != B.val)
        return false;
    //继续往下遍历比较
    return recur(A.left, B.left) && recur(A.right, B.right);
}

时间复杂度

假设A的节点为n,B的节点为m。isSubStructure方法遍历了树A,recur方法遍历了树B。

所以时间复杂度为O(mn)

空间复杂度

由于用到了递归,用到了堆栈帧,之前说过和最大递归深度成正比,而且A的节点数肯定大于等于B,所以空间复杂度为O(n)

感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—码上积木❤️ 每日一个知识点,建立完整体系架构。

本文分享自微信公众号 - 码上积木(Lzjimu),作者:积木zz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [剑指offer] 树的子结构

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    尾尾部落
  • 树的子结构

    题目:输入两棵二叉树A和B,判断B是不是A的子结构。 二叉树结点的定义如下: struct BinaryTreeNode { int ...

    猿人谷
  • [剑指offer][Java]树的子结构

    https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88 输入两棵...

    蛮三刀酱
  • Day17:树的子结构

      对于二叉树来说遍历的时候最好是利用递归的方法。 1、首先设置标志位result = false,因为一旦匹配成功result就设为true。剩下的代码不会...

    一计之长
  • 剑指Offer面试题:17.树的子结构

      为了方便测试,这里封装了一个设置指定根节点的左孩子和右孩子节点的方法:SetSubTreeNode

    Edison Zhou
  • 每日一题 剑指offer(树的子结构)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 二叉树问题(一)-LeetCode 110、617、101、814、655、98、654(递归思路)

    给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

    算法工程师之路
  • 14种模式搞定面试算法编程题(PART I)

    面试锦囊系列一直有收到大家的反馈,包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等,非常高兴小破号的这些整理分享能够真正地帮助到大家

    NewBeeNLP
  • 3道题彻底搞定:套路解决递归问题

    相信不少同学和我一样,在刚学完数据结构后开始刷算法题时,遇到递归的问题总是很头疼,而一看解答,却发现大佬们几行递归代码就优雅的解决了问题。从我自己的学习经历来看...

    灵魂画师牧码
  • 【leetcode刷题】T144-另一个树的子树

    给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它...

    木又AI帮
  • 剑指offer 树的子结构

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    week
  • 【剑指Offer】树的子结构

    4 / 1 返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

    小新哟
  • 剑指offer--树的子结构

    题目描述 输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    AI那点小事
  • 牛客网-树的子结构

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    TrueDei
  • C++版 - 剑指offer 面试题18: 树的子结构(LintCode 245.Subtree) 题解

    提交网址: http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=1...

    Enjoy233
  • 二叉树构建与遍历-LeetCode 889、1008、129、113

    返回与给定的前序和后序遍历匹配的任何二叉树。 pre 和 post 遍历中的值是不同的正整数。

    算法工程师之路
  • 二叉树问题(二)-LeetCode 965、563、993、958、919(树深度,层次遍历)

    如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时,才返回 true;否则返回 false。

    算法工程师之路
  • N叉树问题-LeetCode 429、589、590、105、106(构建二叉树,N叉树遍历)

    给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。 例如,给定一个 3叉树 :

    算法工程师之路
  • LeetCode1-120题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到120道题了。今天把发布的1-120篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈

扫码关注云+社区

领取腾讯云代金券