c++ 图论2 深度优先算法和广度优先算法
修改一下深度优先算法和广度优先算法,标出每一个节点相对于遍历起始位置的层级,遍历起始起点为第一层,和第一层相连的节点为第二层,以此类推
定义一个新的结构
struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(TreeNode* n, int l) : node(n), level(l) {}
};
深度优先搜索(DFS)
class Solution {
public:vector<NodeWithLevel> dfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;dfsHelper(root, 1, result);return result;}private:void dfsHelper(TreeNode* node, int level, vector<NodeWithLevel>& result) {if (node == nullptr) {return;}// 将当前节点及其层级添加到结果中result.push_back(NodeWithLevel(node, level));// 递归处理左子树,层级加1dfsHelper(node->left, level + 1, result);// 递归处理右子树,层级加1dfsHelper(node->right, level + 1, result);}
};
DFS算法的工作原理:
- 我们使用一个辅助函数
dfsHelper,它接受当前节点、当前层级和结果vector作为参数。 - 如果当前节点为空,我们直接返回。
- 我们将当前节点和其层级添加到结果中。
- 然后我们递归地处理左子树和右子树,每次递归时层级加1。
广度优先搜索(BFS):
class Solution {
public:vector<NodeWithLevel> bfsWithLevel(TreeNode* root) {vector<NodeWithLevel> result;if (root == nullptr) {return result;}queue<NodeWithLevel> q;q.push(NodeWithLevel(root, 1));while (!q.empty()) {NodeWithLevel current = q.front();q.pop();// 将当前节点及其层级添加到结果中result.push_back(current);// 如果左子节点存在,将其加入队列,层级加1if (current.node->left) {q.push(NodeWithLevel(current.node->left, current.level + 1));}// 如果右子节点存在,将其加入队列,层级加1if (current.node->right) {q.push(NodeWithLevel(current.node->right, current.level + 1));}}return result;}
};
这个BFS算法的工作原理:
- 我们创建一个队列来存储
NodeWithLevel对象。 - 我们从根节点开始,将其作为第一层加入队列。
- 当队列不为空时,我们取出队首元素,将其添加到结果中。
- 然后我们检查当前节点的左右子节点,如果存在,就将它们加入队列,层级为当前节点的层级加1。
- 重复这个过程直到队列为空。
这两种算法都会返回一个 vector<NodeWithLevel>,其中包含了树中所有节点及其对应的层级。DFS 通常会以前序遍历的顺序返回节点,而 BFS 会按照层序遍历的顺序返回节点。
相关文章:
c++ 图论2 深度优先算法和广度优先算法
修改一下深度优先算法和广度优先算法,标出每一个节点相对于遍历起始位置的层级,遍历起始起点为第一层,和第一层相连的节点为第二层,以此类推 定义一个新的结构 struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(T…...
【Qt】初识QtQt Creator
一.简述Qt 1.什么是Qt Qt 是⼀个 跨平台的 C 图形⽤⼾界⾯应⽤程序框架 。它为应⽤程序开发者提供了建⽴艺术级图形界⾯所需的所有功能。它是完全⾯向对象的,很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式,开发者可以通过简单的拖拽和组合来实现…...
Android 11.0 修改系统显示大小导航栏消失
Android 11.0 修改系统显示大小导航栏消失 1.显示大小设置为大时,导航栏图标不显示。 设置为大,较大,最大时,导航栏图标不显示。 2.开始怀疑是导航栏被隐藏了,各种折腾无效。 3.发现: frameworks/base/pa…...
RocketMQ源码学习笔记:Producer启动流程
这是本人学习的总结,主要学习资料如下 马士兵教育rocketMq官方文档 目录 1、Overview1.1、创建MQClientInstance1.1.1、检查1.1.1、MQClientInstance的ID 1.2、MQClientInstance.start() 1、Overview 这是发送信息的代码样例, DefaultMQProducer produ…...
Node.js 和浏览器环境中都使用 WebSocket
使用WebSocket为什么不适配双端 浏览器环境本身就支持 WebSocket,直接使用 JavaScript 内置的 WebSocket 对象来建立连接。 Node中本身并没有内置 WebSocket 协议的支持,所以需要使用第三方库 ws来实现 WebSocket 功能。 一. 使用跨平台 WebSocket 库 …...
css美化滚动条样式
效果展示 实现 滚动条宽,高度 /* 整体滚动条 */ ::-webkit-scrollbar {width: 10px; }/* 滚动条轨道 */ ::-webkit-scrollbar-track {background-color: #ffffff;border-radius: 6px; }/* 滚动条滑块 */ ::-webkit-scrollbar-thumb {background-color: #888;borde…...
由浅入深,走进深度学习(补充篇:转置卷积和FCN)
本期内容是针对神经网络层结构的一个补充,主要内容是:转置卷积和全连接卷积网络 相关内容: 由浅入深,走进深度学习(2)_卷积层-CSDN博客 由浅入深,走进深度学习(补充篇:…...
Linux基础篇——目录结构
基本介绍 Linux的文件系统是采用级层式的树状目录结构,在此结构中的最上层是根目录"/",然后在根目录下再创建其他的目录 在Linux中,有一句经典的话:在Linux世界里,一切皆文件 Linux中根目录下的目录 具体的…...
星际编码:Swifter.Json,.NET宇宙中的数据处理新星
概述 在数字化的星辰大海中,数据是宇宙的通用语言。在.NET这一广袤的星系中,JSON作为信息交换的媒介,扮演着至关重要的角色。今天,我们要探索的是一颗新星——Swifter.Json,一个功能全面且性能卓越的JSON序列化和反序列…...
python 压缩数据
requests 是 Python 中一个非常流行的 HTTP 库,用于发送各种 HTTP 请求。下面是一个使用 requests 库发送简单 GET 请求和 POST 请求的示例: 首先,确保你已经安装了 requests 库。如果还没有安装,可以使用 pip 进行安装ÿ…...
nacos在k8s上的集群安装实践
目录 概述实践nfs安装使用 k8s持久化nacos安装创建角色部署数据库执行数据库初始化语句部署nacos ingress效果展示问题修复 结束 概述 本文主要对 nacos 在k8s上的集群安装 进行说明与实践。主要版本信息,k8s: 1.27.x,nacos: 2.0.3。运行环境为 centos 7…...
数据结构—判断题
1.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。 答案:错误 2.(neuDS)在顺序表中逻辑上相邻的元素,其对应的物理位置也是相邻的。 答案:正确 3.若一个栈的输入序列为{1, 2, 3, 4, 5},则不…...
树莓派挂载的移动硬盘badblocks坏道屏蔽,以这个为准
!!!use 这里要设置块大小和磁盘相同 badblocks -b 4096 -s -c 512 -v -o /a/2/bads4.txt /dev/sda5 检测完重新检测跳过之前的记录 badblocks -i /a/2/bads4.txt -b 4096 -s -c 512 -v -o /a/2/bads5.txt /dev/sda5 可以查看磁盘具体block总数和大小 sudo dumpe2fs /dev/sda5 …...
Unity开箱即用的UGUI面板的拖拽移动功能
文章目录 👉一、背景👉二、效果图👉三、原理👉四、核心代码👉五,总结 👉一、背景 之前做PC项目时常常有面板拖拽移动的需求,今天总结封装一下,做成一个随时随地可复用的…...
春秋云境:CVE-2022-25411[漏洞复现]
根据题目提示和CNNVD优先寻找后台管理地址 靶机启动后,使用AWVS进行扫描查看网站结构 在这里可以看到后台管理的登录地址:/admin/,根据题目提示可知是弱口令 尝试admin、123456、admin666、admin123、admin888...等等常见弱口令 正确的账户…...
java基础知识点全集
JAVA的所有知识点 一、基础的数组、数据类型、输入输出二、类与对象1. 三大特征(1) 封装(2)继承(3)多态 2. 类的实例化(1) 类通过NEW来创建(2) 类的继承&…...
如何完成域名解析验证
一:什么是DNS解析: DNS解析是互联网上将人类可读的域名(如www.example.com)转换为计算机可识别的IP地址(如192.0.2.1)的过程,大致遵循以下步骤: 查询本地缓存:当用户尝…...
2024年6月个人工作生活总结
title: 2024年6月个人工作生活总结 urlname: code-for-2024-06 tags: 代码积累知识总结 categories:我的程序代码 date: 2024-06-30 00:00:00 photos:gallery/tech/c2.jpg 本文为 2024年6月工作生活总结。 研发编码 编码和注释 因某些需要,重拾了2019年的工程代码…...
Json与Java类
简介 JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。JSON数据由键值对构成,并以易于阅读的文本形式展现,支持数组、对象、字符串、数字、布尔值…...
动手学深度学习(Pytorch版)代码实践 -计算机视觉-39实战Kaggle比赛:狗的品种识别(ImageNet Dogs)
39实战Kaggle比赛:狗的品种识别(ImageNet Dogs) 比赛链接:Dog Breed Identification | Kaggle 1.导入包 import torch from torch import nn import collections import math import os import shutil import torchvision from…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
