当前位置: 首页 > 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 会按照层序遍历的顺序返回节点。

http://www.lryc.cn/news/388215.html

相关文章:

  • 【Qt】初识QtQt Creator
  • Android 11.0 修改系统显示大小导航栏消失
  • RocketMQ源码学习笔记:Producer启动流程
  • Node.js 和浏览器环境中都使用 WebSocket
  • css美化滚动条样式
  • 由浅入深,走进深度学习(补充篇:转置卷积和FCN)
  • Linux基础篇——目录结构
  • 星际编码:Swifter.Json,.NET宇宙中的数据处理新星
  • python 压缩数据
  • nacos在k8s上的集群安装实践
  • 数据结构—判断题
  • 树莓派挂载的移动硬盘badblocks坏道屏蔽,以这个为准
  • Unity开箱即用的UGUI面板的拖拽移动功能
  • 春秋云境:CVE-2022-25411[漏洞复现]
  • java基础知识点全集
  • 如何完成域名解析验证
  • 2024年6月个人工作生活总结
  • Json与Java类
  • 动手学深度学习(Pytorch版)代码实践 -计算机视觉-39实战Kaggle比赛:狗的品种识别(ImageNet Dogs)
  • 在Linux系统中挂载硬盘
  • 安卓短视频去水印v1.7 简洁好用
  • 【征服数据结构】:期末通关秘籍
  • GIT 基于master分支创建hotfix分支的操作
  • Vue-CLI脚手架与node.js安装
  • 自适应站长跑路单页网站源码
  • Java基础(判断和循环)
  • 51单片机第12步_使用stdio.h库函数仿真串口通讯
  • simulink-esp32开发foc电机
  • Python教程--基本技能
  • 干货分享:Spring中经常使用的工具类(提示开发效率)