题目描述
输入两棵二叉树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
...有大把时间,当然你可以选择「 刷剧 」,然而,「 学好算法 」,三年后的你自然「 不能同日而语 」。 那么这里,我整理了「 几十个基础算法 」 的分类,点击开启: ?《算法入门指引》? 如果链接被屏蔽,或者有权...
...5 仔细观察发现这个序列和树的中序遍历是一样的,所以算法就好写了,先中序遍历得到一个序列,然后再按照双向链表的指针规则链接起来即可。 代码实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } ...
...互不相交的有限集T1,T2,T3,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树(Subtree)。 例如,(a)是只有一个根结点的树;(b)是有13个结点的树,其中A是根,其余结点分成3个互不相交的子集:T1={B,E,F,K,L},t2={D,H,I,J,M...
...对象来描述这个节点 react diff 与传统树的diff的区别 计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n^3) react d...
题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 递归解法 function TreeNode(x) { this.val = x; this.left = null; this.right = null; } f...
阅读 2944·2021-11-25 09:43
阅读 2669·2021-10-08 10:04
阅读 1303·2019-08-26 12:20
阅读 1703·2019-08-26 12:09
阅读 183·2019-08-23 18:25
阅读 3310·2019-08-23 17:54
阅读 1956·2019-08-23 17:50
阅读 513·2019-08-23 14:33