资讯专栏INFORMATION COLUMN

【刷算法】一棵树是否是另一棵树的子结构

Chaz / 1702人阅读

题目描述

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

分析

假设树A的根节点ra和树B的根节点rb值相同,那么接下来就以这两个节点开始依次比较ra.left和rb.left、ra.right和rb.right,过程中只要有一个不相同则返回;继续比较ra.left和rb是否相同、ra.right和rb是否相同,就这样依次进行下去,时间复杂度则为O(树A的节点数)*O(树B的节点数)

代码实现
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(r1, r2)
{    
    if(r1 === null || r2 === null)
        return false;
    return check(r1, r2) || HasSubtree(r1.left, r2) || HasSubtree(r1.right, r2);
}
function check(a,b){
    if(b === null)
        return true;
    if(a === null || a.val !== b.val)
        return false;
    return check(a.left, b.left) && check(a.right, b.right);
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/108115.html

相关文章

  • 算法入门⭐《二叉树 - 二叉搜索树》简单05 —— LeetCode 897. 递增顺序搜索树

    ...有大把时间,当然你可以选择「 剧 」,然而,「 学好算法 」,三年后你自然「 不能同日而语 」。   那么这里,我整理了「 几十个基础算法分类,点击开启: ?《算法入门指引》?  如果链接被屏蔽,或者有权...

    Soarkey 评论0 收藏0
  • 算法】二叉搜索树与双向链表

    ...5 仔细观察发现这个序列和树中序遍历是一样,所以算法就好写了,先中序遍历得到一个序列,然后再按照双向链表指针规则链接起来即可。 代码实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } ...

    FreeZinG 评论0 收藏0
  • js 中二叉树深度遍历与广度遍历(递归实现与非递归实现)

    ...互不相交有限集T1,T2,T3,...Tm,其中每一个集合本身又是棵树,并且称为根子树(Subtree)。 例如,(a)是只有一个根结点树;(b)是有13个结点树,其中A是根,其余结点分成3个互不相交子集:T1={B,E,F,K,L},t2={D,H,I,J,M...

    Yuanf 评论0 收藏0
  • 【React进阶系列】 虚拟dom与diff算法

    ...对象来描述这个节点 react diff 与传统树diff区别 计算棵树结构转换成另棵树结构最少操作,是一个复杂且值得研究问题。传统 diff 算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n^3) react d...

    zhou_you 评论0 收藏0
  • 算法】求二叉树深度递归以及非递归解法

    题目描述 输入一棵二叉树,求该树深度。从根结点到叶结点依次经过结点(含根、叶结点)形成树一条路径,最长路径长度为树深度。 递归解法 function TreeNode(x) { this.val = x; this.left = null; this.right = null; } f...

    Carl 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<