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

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算法的工作原理:

  1. 我们使用一个辅助函数 dfsHelper,它接受当前节点、当前层级和结果vector作为参数。
  2. 如果当前节点为空,我们直接返回。
  3. 我们将当前节点和其层级添加到结果中。
  4. 然后我们递归地处理左子树和右子树,每次递归时层级加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算法的工作原理:

  1. 我们创建一个队列来存储 NodeWithLevel 对象。
  2. 我们从根节点开始,将其作为第一层加入队列。
  3. 当队列不为空时,我们取出队首元素,将其添加到结果中。
  4. 然后我们检查当前节点的左右子节点,如果存在,就将它们加入队列,层级为当前节点的层级加1。
  5. 重复这个过程直到队列为空。

这两种算法都会返回一个 vector<NodeWithLevel>,其中包含了树中所有节点及其对应的层级。DFS 通常会以前序遍历的顺序返回节点,而 BFS 会按照层序遍历的顺序返回节点。

相关文章:

c++ 图论2 深度优先算法和广度优先算法

修改一下深度优先算法和广度优先算法&#xff0c;标出每一个节点相对于遍历起始位置的层级&#xff0c;遍历起始起点为第一层&#xff0c;和第一层相连的节点为第二层&#xff0c;以此类推 定义一个新的结构 struct NodeWithLevel {TreeNode* node;int level;NodeWithLevel(T…...

【Qt】初识QtQt Creator

一.简述Qt 1.什么是Qt Qt 是⼀个 跨平台的 C 图形⽤⼾界⾯应⽤程序框架 。它为应⽤程序开发者提供了建⽴艺术级图形界⾯所需的所有功能。它是完全⾯向对象的&#xff0c;很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式&#xff0c;开发者可以通过简单的拖拽和组合来实现…...

Android 11.0 修改系统显示大小导航栏消失

Android 11.0 修改系统显示大小导航栏消失 1.显示大小设置为大时&#xff0c;导航栏图标不显示。 设置为大&#xff0c;较大&#xff0c;最大时&#xff0c;导航栏图标不显示。 2.开始怀疑是导航栏被隐藏了&#xff0c;各种折腾无效。 3.发现&#xff1a; frameworks/base/pa…...

RocketMQ源码学习笔记:Producer启动流程

这是本人学习的总结&#xff0c;主要学习资料如下 马士兵教育rocketMq官方文档 目录 1、Overview1.1、创建MQClientInstance1.1.1、检查1.1.1、MQClientInstance的ID 1.2、MQClientInstance.start() 1、Overview 这是发送信息的代码样例&#xff0c; DefaultMQProducer produ…...

Node.js 和浏览器环境中都使用 WebSocket

使用WebSocket为什么不适配双端 浏览器环境本身就支持 WebSocket&#xff0c;直接使用 JavaScript 内置的 WebSocket 对象来建立连接。 Node中本身并没有内置 WebSocket 协议的支持&#xff0c;所以需要使用第三方库 ws来实现 WebSocket 功能。 一. 使用跨平台 WebSocket 库 …...

css美化滚动条样式

效果展示 实现 滚动条宽&#xff0c;高度 /* 整体滚动条 */ ::-webkit-scrollbar {width: 10px; }/* 滚动条轨道 */ ::-webkit-scrollbar-track {background-color: #ffffff;border-radius: 6px; }/* 滚动条滑块 */ ::-webkit-scrollbar-thumb {background-color: #888;borde…...

由浅入深,走进深度学习(补充篇:转置卷积和FCN)

本期内容是针对神经网络层结构的一个补充&#xff0c;主要内容是&#xff1a;转置卷积和全连接卷积网络 相关内容&#xff1a; 由浅入深&#xff0c;走进深度学习&#xff08;2&#xff09;_卷积层-CSDN博客 由浅入深&#xff0c;走进深度学习&#xff08;补充篇&#xff1a…...

Linux基础篇——目录结构

基本介绍 Linux的文件系统是采用级层式的树状目录结构&#xff0c;在此结构中的最上层是根目录"/"&#xff0c;然后在根目录下再创建其他的目录 在Linux中&#xff0c;有一句经典的话&#xff1a;在Linux世界里&#xff0c;一切皆文件 Linux中根目录下的目录 具体的…...

星际编码:Swifter.Json,.NET宇宙中的数据处理新星

概述 在数字化的星辰大海中&#xff0c;数据是宇宙的通用语言。在.NET这一广袤的星系中&#xff0c;JSON作为信息交换的媒介&#xff0c;扮演着至关重要的角色。今天&#xff0c;我们要探索的是一颗新星——Swifter.Json&#xff0c;一个功能全面且性能卓越的JSON序列化和反序列…...

python 压缩数据

requests 是 Python 中一个非常流行的 HTTP 库&#xff0c;用于发送各种 HTTP 请求。下面是一个使用 requests 库发送简单 GET 请求和 POST 请求的示例&#xff1a; 首先&#xff0c;确保你已经安装了 requests 库。如果还没有安装&#xff0c;可以使用 pip 进行安装&#xff…...

nacos在k8s上的集群安装实践

目录 概述实践nfs安装使用 k8s持久化nacos安装创建角色部署数据库执行数据库初始化语句部署nacos ingress效果展示问题修复 结束 概述 本文主要对 nacos 在k8s上的集群安装 进行说明与实践。主要版本信息&#xff0c;k8s: 1.27.x&#xff0c;nacos: 2.0.3。运行环境为 centos 7…...

数据结构—判断题

1.数据的逻辑结构说明数据元素之间的顺序关系&#xff0c;它依赖于计算机的存储结构。 答案&#xff1a;错误 2.(neuDS)在顺序表中逻辑上相邻的元素&#xff0c;其对应的物理位置也是相邻的。 答案&#xff1a;正确 3.若一个栈的输入序列为{1, 2, 3, 4, 5}&#xff0c;则不…...

树莓派挂载的移动硬盘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面板的拖拽移动功能

文章目录 &#x1f449;一、背景&#x1f449;二、效果图&#x1f449;三、原理&#x1f449;四、核心代码&#x1f449;五&#xff0c;总结 &#x1f449;一、背景 之前做PC项目时常常有面板拖拽移动的需求&#xff0c;今天总结封装一下&#xff0c;做成一个随时随地可复用的…...

春秋云境:CVE-2022-25411[漏洞复现]

根据题目提示和CNNVD优先寻找后台管理地址 靶机启动后&#xff0c;使用AWVS进行扫描查看网站结构 在这里可以看到后台管理的登录地址&#xff1a;/admin/&#xff0c;根据题目提示可知是弱口令 尝试admin、123456、admin666、admin123、admin888...等等常见弱口令 正确的账户…...

java基础知识点全集

JAVA的所有知识点 一、基础的数组、数据类型、输入输出二、类与对象1. 三大特征&#xff08;1&#xff09; 封装&#xff08;2&#xff09;继承&#xff08;3&#xff09;多态 2. 类的实例化&#xff08;1&#xff09; 类通过NEW来创建&#xff08;2&#xff09; 类的继承&…...

如何完成域名解析验证

一&#xff1a;什么是DNS解析&#xff1a; DNS解析是互联网上将人类可读的域名&#xff08;如www.example.com&#xff09;转换为计算机可识别的IP地址&#xff08;如192.0.2.1&#xff09;的过程&#xff0c;大致遵循以下步骤&#xff1a; 查询本地缓存&#xff1a;当用户尝…...

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月工作生活总结。 研发编码 编码和注释 因某些需要&#xff0c;重拾了2019年的工程代码…...

Json与Java类

简介 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解析和生成。JSON数据由键值对构成&#xff0c;并以易于阅读的文本形式展现&#xff0c;支持数组、对象、字符串、数字、布尔值…...

动手学深度学习(Pytorch版)代码实践 -计算机视觉-39实战Kaggle比赛:狗的品种识别(ImageNet Dogs)

39实战Kaggle比赛&#xff1a;狗的品种识别&#xff08;ImageNet Dogs&#xff09; 比赛链接&#xff1a;Dog Breed Identification | Kaggle 1.导入包 import torch from torch import nn import collections import math import os import shutil import torchvision from…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...