当前位置: 首页 > news >正文

有趣且重要的JS知识合集(22)树相关的算法

0、举例:树形结构原始数据

 1、序列化树形结构 

/*** 平铺序列化树形结构* @param tree 树形结构* @param result 转化后一维数组* @returns Array<TreeNode>*/
export function flattenTree(tree, result = []) {if (tree.length === 0) {return result}for (const node of tree) {result.push(node);if (node.children) {flattenTree(node.children, result);}}return result;
}

结果:

2、数组转化为树形结构

/*** 数组转化为树形结构(常用于后台菜单数组转换成树形结构)*/
export function arrToTree(data) {let result = []let map = new Map()data.forEach(item => {// 存入字典集里map.set(item.id, item)})data.forEach(item => {item.children = [];// 判断字典集里是否有该键let parent = map.get(item.pId)if (parent) {parent.children.push(item)} else {result.push(item)}})return result
}

结果:

 

 3、BFS 寻找树形结构下指定节点id 上属直接或间接的祖先节点

    /*** 寻找树形结构下指定节点id 上属直接或间接的祖先节点* @param {*} tree 树形结构* @param {*} id 节点id*/bfsFindAncestors(tree, id) {if (!tree?.length) return [];// 初始化队列,将根节点和空的祖先数组放入队列const queue = [{ node: tree[0], ancestors: [] }];while (queue.length > 0) {// 取出队列中的第一个节点和其祖先数组const { node, ancestors } = queue.shift();if (node.id === id) {// 找到目标节点,返回该节点及其祖先节点的数组return ancestors;}if (node.children && node.children.length > 0) {// 将当前节点添加到子节点的祖先数组中const newAncestors = [...ancestors, node];for (const child of node.children) {// 将子节点和新的祖先数组加入队列queue.push({ node: child, ancestors: newAncestors });}}}// 如果遍历完整个树都没有找到目标节点,返回空数组return [];}

 4、BFS 遍历树形结构 寻找对应id的节点

    /*** BFS遍历树形结构 寻找对应id的节点* @param {*} tree 树形结构* @param {*} id 节点id*/getNode(tree, id) {const queue = [...tree];while (queue.length) {const node = queue.shift();if (node.id === id) return node;if (node.children?.length) {queue.push(...node.children);}}return null;}

5、BFS 遍历树结构 给节点某属性赋值

    /*** 遍历树结构 给节点某属性赋值 BFS* @param {*} tree 树形结构* @param {*} prop 属性* @param {*} value 值*/traverseTreeSetProperty(tree, prop, value) {// 定义一个队列,用于存储待处理的节点const queue = [...tree];while (queue.length > 0) {// 出队列const node = queue.shift();// 给当前节点赋值node[prop] = value;// 将当前节点的子节点入队列if (node.children && node.children.length > 0) {queue.push(...node.children);}}}

6、BFS 计算树形结构的最大宽度

    /*** 计算树形结构的最大宽度 BFS* @param {*} tree 树形结构*/getMaxWidth(tree) {if (!tree || tree.length === 0) {return 0;}let maxWidth = 0;let queue = [...tree];while (queue.length > 0) {const levelSize = queue.length;maxWidth = Math.max(maxWidth, levelSize);const nextLevel = [];for (let i = 0; i < levelSize; i++) {const node = queue[i];if (node.children && node.children.length > 0) {nextLevel.push(...node.children);}}queue = nextLevel;}return maxWidth;}

7、DFS 计算树形结构的最大深度

    /*** 计算树形结构的最大深度 DFS* @param {*} tree 树形结构*/getMaxDepth(tree) {const dfs = (nodes) => {// 一级节点为空,层级则为0if (!nodes?.length) return 0;let maxDepth = 1;// eslint-disable-next-linefor (const node of nodes) {const curDepth = dfs(node.children) + 1;maxDepth = Math.max(curDepth, maxDepth);}return maxDepth;}const treeHeight = dfs(tree)return treeHeight;}

8、DFS 寻找指定节点id对应的父级节点

    /*** 寻找指定节点id对应的父级节点* @param {*} tree* @param {*} nodeId*/findParentByChildId(tree, nodeId) {let parentOfFirstChild = null;const dfs = (node, parent) => {if (parentOfFirstChild !== null) {return;}if (node.children && node.children.length > 0) {// eslint-disable-next-linefor (const child of node.children) {dfs(child, node);}}// 找到对应节点后,返回其父节点if (node.id === nodeId) parentOfFirstChild = parent;}// eslint-disable-next-linefor (const node of tree) {dfs(node, null);}return parentOfFirstChild}

9、DFS 寻找第一个叶子节点及对应的父节点

    /*** 寻找第一个叶子节点及叶子节点的父节点* @param {*} tree*/findFirstChildAndParent(tree) {let firstChild = null;let parentOfFirstChild = null;const dfs = (node, parent) => {if (firstChild !== null) {return; // 如果已经找到了第一个子节点,则不再继续搜索}if (node.children && node.children.length > 0) {for (const child of node.children) {dfs(child, node);}} else {firstChild = node;parentOfFirstChild = parent;}}for (const node of tree) {dfs(node, null);}return {firstChild,parentOfFirstChild};}

相关文章:

有趣且重要的JS知识合集(22)树相关的算法

0、举例&#xff1a;树形结构原始数据 1、序列化树形结构 /*** 平铺序列化树形结构* param tree 树形结构* param result 转化后一维数组* returns Array<TreeNode>*/ export function flattenTree(tree, result []) {if (tree.length 0) {return result}for (const …...

使用 Let’s Encrypt 生成免费 SSL 证书

使用 Let’s Encrypt 生成证书是一个简单且免费的方式&#xff0c;可以通过 Certbot 工具来实现。以下是详细的步骤说明&#xff1a; 1. 安装 Certbot 根据你的操作系统&#xff0c;安装 Certbot。以下以 Ubuntu 为例&#xff1a; sudo apt update sudo apt install certbot…...

【电脑小白】装机从认识电脑部件开始

前言 在 B 站上刷到了一个很牛逼的电脑装机视频&#xff0c;很适合电脑小白学习&#xff0c;故用文本记录下。 推荐对组装台式电脑有兴趣的小伙伴都去看看这个视频&#xff1a; 原视频链接&#xff1a;【装机教程】全网最好的装机教程&#xff0c;没有之一_哔哩哔哩_bilibil…...

ssldump一键分析网络流量(KALI工具系列二十二)

目录 1、KALI LINUX 简介 2、ssldump工具简介 3、在KALI中使用ssldump 3.1 目标主机IP&#xff08;win&#xff09; 3.2 KALI的IP 4、操作示例 4.1 监听指定网卡 4.2 指定端口 4.3 特定主机 4.4 解码文件 4.5 显示对话摘要 4.6 显示加密数据&#xff08;需要私钥&…...

使用seq2seq架构实现英译法

seq2seq介绍 模型架构&#xff1a; Seq2Seq&#xff08;Sequence-to-Sequence&#xff09;模型是一种在自然语言处理&#xff08;NLP&#xff09;中广泛应用的架构&#xff0c;其核心思想是将一个序列作为输入&#xff0c;并输出另一个序列。这种模型特别适用于机器翻译、聊天…...

攻防演练“轻装上阵” | 亚信安全信舱ForCloud 打造全栈防护新策略

网络世界攻防实战中&#xff0c;攻击风险已经从代码到云横跨全栈技术点&#xff0c;你准备好了吗 云服务器&#xff0c;攻击众矢之的 2022年超过38万个Kubernetes API服务器暴露公网&#xff0c;成为攻击者目标。云服务器&#xff0c;尤其是开源设施&#xff0c;一直以来不仅是…...

在Android Studio中将某个文件移出Git版本管理

最新在整理代码时发现&#xff0c;local.properties文件开头有这么一段注释&#xff1a; ## This file must *NOT* be checked into Version Control Systems, # as it contains information specific to your local configuration. 大意是这个文件不要加入到版本管理中。 之…...

Vue46-render函数

一、非单文件和单文件的main.js对比 1-1、非单文件的main.js 1-2、 单文件的main.js 将单文件的main.js中的render函数变成非单文件的main.js中的template形式&#xff0c;报如下错误&#xff1a; 解决方式&#xff1a; 二、解决方式 2-1、引入完成版的vue.js 精简版的vue&a…...

@RequestParam 和 @PathVariable @Param注解的区别和作用

在Spring MVC中&#xff0c;RequestParam、PathVariable和 RequestBody 是用于处理不同类型的请求参数的注解。每个注解都有其特定的用途和用法。让我们分别看一下它们的区别和作用。 RequestParam RequestParam用于从请求参数中获取数据&#xff0c;通常是处理表单数据或URL…...

复习一下。

名词解释 数字图像&#xff1a;数字图像是通过数字技术捕获存储和处理的图像。它由一个矩阵或二维数组的像素组成&#xff0c;每个像素包含图像在该位置上的颜色或亮度信息。 像素&#xff1a;像素是构成数字图像的最小单位。每个像素代表图像中某个位置的颜色或亮度值。 分辨…...

ripro主题如何使用memcached来加速

ripro主题是个很不错的资源付费下载主题。主题自带了缓存加速开关&#xff0c;只要开启了缓存加速功能&#xff0c;正常情况下能让网站访问的速度提升很大。 但好多人这么做了却发现没啥加速效果&#xff0c;原因就在于wordpress里缺少了memcache文件。只需要把object-cache.ph…...

《珊瑚岛》是一款什么类型的游戏 苹果电脑如何玩到《珊瑚岛》

在众多电子游戏中&#xff0c;有些游戏因其独特的游戏体验和丰富的内容而脱颖而出&#xff0c;《珊瑚岛》便是其中之一。在游戏中你将离开宝京前往珊瑚岛&#xff0c;种植农作物、饲养动物、和岛民成为朋友。您不仅可以振兴该岛小镇&#xff0c;还可以保护和修复周围的珊瑚礁。…...

Go - 3.库源码文件

目录 一.引言 二.库源码文件 1.定义 2.生成库源码文件 3.直接调用库源码文件 三.总结 一.引言 前面我们学习了 命令源码文件&#xff0c;并成功运行了 go 的 hello world 代码&#xff0c;下面我们介绍 go 里面另一个概念: 库源码文件。 二.库源码文件 1.定义 库源码文…...

FPGA的基础仿真项目--七段数码管设计显示学号

一、设计实验目的 1&#xff0e; 了解数码管显示模块的工作原理。 2&#xff0e; 熟悉VHDL 硬件描述语言及自顶向下的设计思想。 3&#xff0e; 掌握利用FPGA设计6位数码管扫描显示驱动电路的方法。 二、实验设备 1. PC机 2.Cyclone IV FPGA开发板 三、扫描原理 下图所…...

Jmeter接口请求之 :multipart/form-data 参数请求

参考教程 Jmeter压测之&#xff1a;multipart/form-data_jmeter form-data-CSDN博客 1、通过fiddler对接口进行抓取&#xff0c;接口信息如下图所示 2、获取到接口后 在fiddler右侧点击Inspectors-Raw中可以看到如下图所示信息&#xff0c;上半部分为默认请求头信息内容&#…...

Type-C诱骗芯片LDR6500

随着科技的飞速发展&#xff0c;电子设备的智能化和便携化已成为趋势。在这个过程中&#xff0c;Type-C接口因其高速传输、正反可插以及强大的扩展能力&#xff0c;逐渐成为主流接口标准。然而&#xff0c;Type-C接口的广泛应用也带来了一系列挑战&#xff0c;其中之一便是如何…...

统一异常处理

问题 当系统出现异常时&#xff0c;除了要在控制台、日志等后台进行输出之外&#xff0c;还需要在前端提示用户。 为了提示给用户&#xff0c;错误信息需要做一些约定&#xff1a; 错误信息统一用json格式返回给前端以HTTP状态码判断是否出现异常&#xff0c;非200即为异常 …...

Nginx网络服务

1 Nginx服务基础 Nginx&#xff08; 发音为&#xff3b;engine x] ) 专为性能优化而开发&#xff0c;其最知名的优点是它的稳定性和低系 统资源消耗&#xff0c; 以及对HTTP 并发连接的高处理能力&#xff08;单台物理服务器可支持30000~50000 个并发请求&#xff09; 。正因为…...

ifconfig eth0 hw ether

ifconfig hw ether 是一个用于在 Linux 系统中设置或更改网络接口的硬件地址&#xff08;即 MAC 地址&#xff09;的命令。具体操作步骤如下&#xff1a; 首先&#xff0c;您需要确定要更改 MAC 地址的网络接口名称&#xff0c;通常是 eth0, eth1 等&#xff0c;取决于您的系统…...

微信小程序录音机源代码

<!-- <button bind:tap"startTab">开始录音</button> <button bind:tap"stopTab">结束录音</button> <button bind:tap"playTab">播放录音</button> <view style"margin: 0 auto;">{{ti…...

深入解析Shim在跨版本API兼容中的实战应用

1. 什么是Shim技术 第一次听到"Shim"这个词是在调试一个Flink连接Hive的项目时。当时Hive版本从2.3升级到3.1&#xff0c;本以为要重写大量代码&#xff0c;结果同事说"加个Shim就行了"。这种"神奇胶水"般的技术让我印象深刻。 Shim本质上是一种…...

K230目标检测实战:手把手教你用Labelme标注数据并一键转成VOC格式(附避坑指南)

K230目标检测实战&#xff1a;高效数据标注与VOC格式转换全攻略 当你第一次接触K230开发板进行目标检测项目时&#xff0c;数据准备往往是最大的拦路虎。特别是从原始图片到符合AI_Cube要求的VOC格式数据集&#xff0c;这个过程充满了各种"坑"。本文将分享一套经过实…...

MCP3202 12位SPI ADC驱动开发与嵌入式工程实践

1. MCP3202 12位串行ADC嵌入式驱动深度解析与工程实践1.1 芯片特性与系统定位MCP3202 是 Microchip 推出的低功耗、逐次逼近型&#xff08;SAR&#xff09;12位模数转换器&#xff0c;专为嵌入式系统中高精度模拟信号采集场景设计。其核心电气特性如下&#xff1a;参数规格工程…...

深入剖析大数据领域数据分片的优缺点

深入剖析大数据领域数据分片的优缺点 关键词&#xff1a;数据分片、大数据架构、分片策略、水平扩展、分布式系统 摘要&#xff1a;在大数据时代&#xff0c;单台服务器已无法承载海量数据的存储与计算需求&#xff0c;数据分片&#xff08;Sharding&#xff09;作为分布式系统…...

从零到一:手把手教你用海康VisionMaster完成第一个字符识别项目(附完整流程与避坑点)

从零到一&#xff1a;手把手教你用海康VisionMaster完成第一个字符识别项目&#xff08;附完整流程与避坑点&#xff09; 在工业自动化领域&#xff0c;字符识别技术正逐渐成为生产线上的"眼睛"。无论是产品追溯码读取、包装日期检测&#xff0c;还是仪表盘数值记录&…...

5分钟极速部署!Billion Mail容器化方案助力邮件营销升级 [特殊字符]

5分钟极速部署&#xff01;Billion Mail容器化方案助力邮件营销升级 &#x1f680; 【免费下载链接】BillionMail Billion Mail is a future open-source email marketing platform designed to help businesses and individuals manage their email campaigns with ease 项目…...

大语言模型推理能力突破

大语言模型原生推理能力增强课题 目录 大语言模型原生推理能力增强课题 当前LLM深层符号推理的核心瓶颈(结合场景实例) 1. 幻觉频发:符号推理的事实一致性崩塌 2. 自我纠错能力弱:缺乏闭环的校验与修正机制 3. 推理链条易断裂:长程逻辑依赖的一致性丢失 全链路原生推理能…...

wan2.1-vae提示词评估体系:构建BLEU-Style指标量化中文提示词有效性

wan2.1-vae提示词评估体系&#xff1a;构建BLEU-Style指标量化中文提示词有效性 1. 为什么需要评估提示词质量 在AI图像生成领域&#xff0c;提示词的质量直接影响最终生成效果。好的提示词能准确表达创作意图&#xff0c;而模糊或不当的提示词可能导致生成结果与预期不符。特…...

Tailscale打洞失败太慢?手把手教你用Docker部署derper自建中转,告别国际绕行

Tailscale网络优化实战&#xff1a;用Docker自建derper中转节点提升连接速度 Tailscale作为现代零配置组网工具&#xff0c;其基于WireGuard协议的P2P直连特性确实令人惊艳——直到你发现两台设备之间的打洞成功率只有60%&#xff0c;而剩余40%的流量不得不绕行官方位于海外的中…...

避坑指南:ESTUN Editor安装后,TP虚拟示教器bricks.ini配置文件到底在哪?

ESTUN Editor安装后TP虚拟示教器配置文件定位全解析 当你在工业机器人编程中同时安装了ESTUN Editor集成环境和独立TP软件包时&#xff0c;最让人头疼的问题莫过于找不到正确的bricks.ini配置文件。这个问题看似简单&#xff0c;却直接影响着虚拟示教器与机器人控制器的连接稳定…...