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

Chaz 发布于2019-08-26 12:09 / 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);
}

私有云云服务器一棵树用c语言打出一棵树棵树一棵

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

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

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

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

Soarkey 2021-09-10 10:51 评论0 收藏0
【刷算法】二叉搜索树与双向链表

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

FreeZinG 2019-08-22 18:32 评论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 2019-08-23 11:38 评论0 收藏0
【React进阶系列】虚拟dom与diff算法

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

zhou_you 2019-08-23 12:24 评论0 收藏0
【刷算法】求二叉树深度的递归以及非递归解法

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

Carl 2019-08-22 18:13 评论0 收藏0