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

Chaz 发布于2019-08-26 12:09 / 2029人阅读

题目描述

输入两棵二叉树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);
}

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

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

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

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

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目 1、题目描述给你一棵二叉搜索树，请按中序遍历将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。样例输入： [5,3,6,2,4,null,8,1,null,null,nu...

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

摘要：题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。分析如果是这样一棵二叉搜索树： showImg(https://segmentfault.com/img/remote/14600000...

FreeZinG 2019-08-22 18:32 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
【React进阶系列】虚拟dom与diff算法

摘要：通过对树进行层级控制，同一个父节点下的所有子节点。新老集合进行差异化对比，发现，则创建并插入至新集合，删除老集合以此类推，创建并插入和，删除和。虚拟dom Jsx 表面写的是html，其实内部执行的是一段js createElement React.createElement( type, [props], [...children] ) createElement把这个...

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

摘要：题目描述输入一棵二叉树，求该树的深度。递归解法非递归解法原来标识当前层是否遍历完毕当前弹出元素为时，说明一层以及遍历完毕了，所以最后一层的弹出时不能再往队列里面加了题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。递归解法 function TreeNode(x) { this.val = x;...

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