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

二叉树(二)深度遍历和广度遍历

一、层序遍历

广度优先搜索:使用队列,先进先出

模板:

1、定义返回的result和用于辅助的队列

2、队列初始化:

root非空时进队

3、遍历整个队列:大循环while(!que.empty())

记录每层的size以及装每层结果的变量(记得每层循环结束后保存结果的值)

4、遍历每层:小循环for或while(size--)

出1进2:先记录当前即将出队的node

node出队,如果孩子节点非空即进队

  vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;//借助队列来实现queue<TreeNode*>que;//(先进先出,层序遍历)(保存节点指针,孩子信息才不丢失)if(root) //先弹进rootque.push(root);while(!que.empty()){//队列不为空时,都要遍历;没有继续加入的,则说明快要遍历完了int size=que.size(); //保存当前层的大小vector<int> vec;//vec记录每层的节点元素,在循环内定义,不用每次清空//将总遍历切割成一层一层的while(size--){//对一层元素进行操作:出一个根节点(要先记录val),则进两个它的孩子节点(如果有)TreeNode*node=que.front();vec.push_back(node->val);que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}result.push_back(vec);}return result;}

 变式:求层平均值

  vector<double> averageOfLevels(TreeNode* root) {vector<double> result;queue<TreeNode*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size=que.size();//当前层元素个数double sum=0;for(int i=0;i<size;i++){TreeNode* node=que.front(); //先保存sum+=node->val;que.pop();//再弹出if(node->left)//最后进两个que.push(node->left);if(node->right)que.push(node->right);}result.push_back(sum/size);}return result;}

 注意:最后要用到sum/size;所以不能用while(size--),因为size会改变,而要用for循环

同理,每层循环要记录size,就是因为que.size()也会改变

二、深度遍历(前中后序,递归)

深度优先搜索:使用栈,先进后出

模板:

前序:

   void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 根traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}

中序:

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 根traversal(cur->right, vec); // 右
}

后序:

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 根
}

三、对比

1、获取最大深度

 深度优先(前序):

   int getdepth(TreeNode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left);       // 左int rightdepth = getdepth(node->right);     // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}

广度优先:

int maxDepth(TreeNode* root) {//1、定义结果变量和辅助队列int depth=0;queue<TreeNode*> que;//2、队列初始化if(root)que.push(root);//3、大循环并记录每层的sizewhile(!que.empty()){int size=que.size();//4、小循环:遍历一层,存1出1进2while(size--){TreeNode*node=que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);}depth++;}return depth;}

2、获取最小深度 

深度优先(前序):

    int minDepth(TreeNode* root) {if(root==NULL)return 0;int lh=minDepth(root->left);int rh=minDepth(root->right);if(!root->left&&root->right)return 1+rh;if(root->left&&!root->right)return 1+lh;return 1+min(lh,rh);}

考虑仅有一个孩子节点时,返回的应是1+子树的最小深度 

广度优先:

 int minDepth(TreeNode* root) {//1、定义结果变量和辅助队列int depth=0;queue<TreeNode*> que;//2、队列初始化if(root)que.push(root);//3、大循环并记录每层的sizewhile(!que.empty()){int size=que.size();//4、小循环:遍历一层,存1出1进2while(size--){TreeNode*node=que.front();que.pop();if(node->left)que.push(node->left);if(node->right)que.push(node->right);//如果遇到叶子节点了,说明可以完成最小深度计算了if(!node->left&&!node->right)return depth+1;//注意是+1(逻辑上要遍历完一层才+1,这里提前结束就提前加)}depth++;}return depth;}

考虑遇到叶子节点时,就可以返回最小深度了

相关文章:

二叉树(二)深度遍历和广度遍历

一、层序遍历 广度优先搜索&#xff1a;使用队列&#xff0c;先进先出 模板&#xff1a; 1、定义返回的result和用于辅助的队列 2、队列初始化&#xff1a; root非空时进队 3、遍历整个队列&#xff1a;大循环while(!que.empty()) 记录每层的size以及装每层结果的变量&a…...

【算法——双指针】

922. 按奇偶排序数组 II 算法讲解050【必备】双指针技巧与相关题目_哔哩哔哩_bilibili main:vector<int>nums { 3,1,2,4 };int i 0, j 1;int n nums.size() - 1;while (j < nums.size() && i < nums.size()) //如果奇偶任一方排好了&#xff0c;另…...

Rocky Linux 9 中添加或删除某个网卡的静态路由的方法

使用ip命令配置临时路由 添加静态路由 ip route add <目的网络> via <下一跳IP> dev <网卡接口名称>例: 给eth0网卡添加一个到达 192.168.2.0/24 网络&#xff0c;下一跳为 192.168.1.254 的路由 ip route add 192.168.2.0/24 via 192.168.1.254 dev eth0…...

网站建设中常见的网站后台开发语言有哪几种,各自优缺点都是什么?

市场上常见的网站后台开发语言有PHP、Python、JavaScript、Ruby、Java和.NET等。这些语言各有其独特的优缺点&#xff0c;适用于不同的开发场景和需求。以下是对这些语言的具体介绍&#xff1a; PHP 优点&#xff1a;PHP是一种广泛用于Web开发的动态脚本语言&#xff0c;特别适…...

【程序大侠传】应用内存缓步攀升,告警如影随形

前序 在武侠编码的江湖中&#xff0c;内存泄漏犹如隐秘杀手&#xff0c;潜伏于应用程序的各个角落&#xff0c;悄无声息地吞噬着系统资源。若不及时发现和解决&#xff0c;必将导致内存枯竭&#xff0c;应用崩溃。 背景&#xff1a;内存泄漏的由来 内存泄漏&#xff0c;乃程序…...

JavaWEB概述

JavaWEB概述 一、什么是JavaWEB 用Java技术解决web互联网领域的技术栈。要学习JavaWEB首先得知道什么是客户端和服务端 客户端&#xff1a;简而言之&#xff0c;这就是使用方&#xff0c;比如我们下载一个软件去使用&#xff0c;里面有很多我们可以使用的功能&#xff0c;那…...

半结构化知识抽取案例

半结构化知识抽取是指从半结构化数据源&#xff08;如HTML、XML、JSON等&#xff09;中提取有用的信息&#xff0c;并将其转换为更易于理解和使用的知识形式。半结构化数据通常包含一些结构化的标记或标签&#xff0c;但不像完全结构化的数据那样严格。 比如抽取如下网页到neo …...

Oracle Truncate和delete的区别

DropTruncatedelete语句类型 DDl &#xff08;数据定义语言 Data Definition Language DDl &#xff08;数据定义语言 Data Definition Language DML&#xff08;数据操作语言 Data Manipulation Language 速度 快 删除整个表 快 一次性删除 慢 逐行删除 回滚不可不可可del…...

应用层协议 --- HTTP

序言 在上一篇文章中&#xff0c;我们在应用层实现了一个非常简单的自定义协议&#xff0c;我们在我们报文的首部添加了报文的长度并且使用特定的符号分割。但是想做一个成熟&#xff0c;完善的协议是不简单的&#xff0c;今天我们就一起看看我们每天都会用到的 HTTP协议 。 UR…...

网卡Network Interface Card

文章目录 网卡&#xff08;Network Interface Card&#xff0c;简称NIC&#xff09;是一种计算机硬件设备&#xff0c;用于将计算机连接到计算机网络&#xff0c;使计算机能够进行数据通信。它是计算机与外部网络&#xff08;如局域网、互联网&#xff09;之间的接口&#xff0…...

9.1 Linux_I/O_基本知识

文件类型 一切I/O皆文件&#xff0c;文件就是存放在磁盘上面的有序数据的集合。 文件类型&#xff1a; 常规文件 r &#xff1a;就是普通文件目录文件 d &#xff1a;就是目录&#xff0c;是一个索引字符设备文件 c &#xff1a;键盘、鼠标块设备文件 b &#xff1a;U盘、磁…...

[Java]一、面向对象核心编程思想

G:\Java\1.JavaSE 1. 继承 1.1 继承的概述 重点内容:1.知道继承的好处2.会使用继承3.知道继承之后成员变量以及成员方法的访问特点4.会方法的重写,以及知道方法重写的使用场景5.会使用this关键字调用当前对象中的成员6.会使用super关键字调用父类中的成员7.会定义抽象方法以…...

科研绘图系列:R语言多个AUC曲线图(multiple AUC curves)

文章目录 介绍加载R包导入数据数据预处理画图输出结果组图系统信息介绍 多个ROC曲线在同一张图上可以直观地展示和比较不同模型或方法的性能。这种图通常被称为ROC曲线图,它通过比较不同模型的ROC曲线下的面积(AUC)大小来比较模型的优劣。AUC值越大,模型的诊断或预测效果越…...

JavaWeb--纯小白笔记06:使用Idea创建Web项目,Servlet生命周期,注解,中文乱码解决

使用Idea创建一个web项目----详细步骤配置&#xff0c;传送门&#xff1a;http://t.csdnimg.cn/RsOs7 src&#xff1a;放class文件 web&#xff1a;放html文件 out&#xff1a;运行过后产生的文件 一创建一个新的web项目(配置好了后)&#xff1a; 在src创建一个文件…...

jQuery——jQuery的2把利器

1、jQuery 核心函数 ① 简称&#xff1a;jQuery 函数&#xff0c;即为 $ 或者 jQuery ② jQuery 库向外直接暴露的是 $ 或者 jQuery ③ 引入 jQuery 库后&#xff0c;直接使用 $ 即可 当函数用&#xff1a;$&#xff08;xxx&#xff09; 当对象用&#xff1a;$.xxx&#x…...

Day29笔记-Python操作pdfPython发送邮件

一、Python操作PDF【了解】 1.pdf 简介 PDF是Portable Document Format的缩写&#xff0c;这类文件通常使用.pdf作为其扩展名。在日常开发工作中&#xff0c;最容易遇到的就是从PDF中读取文本内容以及用已有的内容生成PDF文档这两个任务。 在Python中&#xff0c;可以使用名为P…...

Seata分布式事务实践

理论篇 什么是事务 关于事务我们一定会想到下面这四大特性: 原子性:所有操作要么全都完成&#xff0c;要么全都失败。 一致性: 保证数据库中的完整性约束和声明性约束。 隔离性:对统一资源的操作不会同时发生的。 持久性:对事务完成的操作最终会持久化到数据库中。 理解&…...

数字IC设计\FPGA 职位经典笔试面试整理--基础篇2

1. 卡诺图 逻辑函数表达式可以使用其最小项相加来表示&#xff0c;用所有的最小项可以转换为卡诺图进行逻辑项化简 卡诺图讲解资料1 卡诺图讲解资料2 卡诺图讲解资料3 最小项的定义 一个函数的某个乘积项包含了函数的全部变量&#xff0c;其中每个变量都以原变量或反变量的形…...

(务必收藏)推荐市面上8款AI自动写文献综述的网站

在当前的学术研究和论文写作中&#xff0c;AI技术的应用已经变得越来越普遍。特别是在文献综述这一环节&#xff0c;AI工具能够显著提高效率并减少人工劳动。以下是市面上8款推荐的AI自动写文献综述的网站&#xff1a; 一、千笔-AIPassPaper 是一款备受好评的AI论文写作平台&…...

【python】运算符

学习目标 了解 Python 中常见 算术&#xff08;数学&#xff09;运算符赋值运算符 算术&#xff08;数学&#xff09;运算符 a 是 10&#xff0c;b 是 20 运算符描述实例加两个对象相加 a b 输出结果 30-减得到负数或是一个数减去另一个数 a - b 输出结果 -10*乘两个数相…...

Mojo调用Python模块性能翻倍?深度剖析混合编程内存管理、GIL绕过与ABI兼容性(附实测基准数据)

第一章&#xff1a;Mojo与Python混合编程案例源码分析Mojo 作为兼具 Python 兼容性与系统级性能的新一代编程语言&#xff0c;其与 Python 的混合编程能力是实际工程落地的关键。以下通过一个典型场景——在 Python 主程序中调用 Mojo 实现的高性能向量加法函数——展开源码级剖…...

8位单片机中16位int型数据操作技巧

8位单片机中对16位int型数据的操作技巧1. 数据合并的需求背景在8位单片机开发中&#xff0c;经常需要处理16位数据。由于8位架构的限制&#xff0c;16位数据需要拆分为两个8位字节进行存储和传输。当需要将两个8位数据合并为一个16位数据时&#xff0c;开发者需要掌握高效可靠的…...

OpenClaw自动化测试:Qwen3-32B批量执行LeetCode题目

OpenClaw自动化测试&#xff1a;Qwen3-32B批量执行LeetCode题目 1. 为什么需要自动化编程能力测试 作为一名长期关注AI编程辅助工具的技术博主&#xff0c;我一直在寻找能够客观评估大模型编程能力的方法。传统的单次对话测试往往带有偶然性&#xff0c;无法系统性地反映模型…...

二分查找/二分答案

0.前言二分算法&#xff08;Binary Search&#xff09;&#xff0c;也叫折半查找&#xff0c;是一种在有序数据集合中高效查找目标值的算法。它通过不断将查找范围缩小一半&#xff0c;快速定位目标&#xff0c;时间复杂度为 O(logn)&#xff0c;远优于线性查找的 O(n)。1.原理…...

【深度解析】DeepSeek API 悄然分叉:开发者该如何正确评估与接入最新大模型?

摘要 本文基于近期 DeepSeek API 更新及官方文档变更&#xff0c;从「API 版本 ≠ Web/App 版本」这一关键细节出发&#xff0c;梳理大模型多版本部署策略背后的技术与成本逻辑&#xff0c;并给出基于兼容 OpenAI 协议的实战接入示例&#xff08;使用 claude‑sonnet‑4‑6&…...

基于LangChain的RAG与Agent智能体开发 - 持久化会话记忆功能实现(RunnableWithMessageHistory+RedisChatMessageHistory)

大家好&#xff0c;我是小锋老师&#xff0c;最近更新《2027版 基于LangChain的RAG与Agent智能体 开发视频教程》专辑&#xff0c;感谢大家支持。本课程主要介绍和讲解RAG&#xff0c;LangChain简介&#xff0c;接入通义千万大模型 &#xff0c;Ollama简介以及安装和使…...

[技术突破]M9A:构建《重返未来:1999》智能自动化解决方案

[技术突破]M9A&#xff1a;构建《重返未来&#xff1a;1999》智能自动化解决方案 【免费下载链接】M9A 1999 小助手 项目地址: https://gitcode.com/gh_mirrors/m9/M9A 实现游戏体验革新的技术价值 M9A作为专为《重返未来&#xff1a;1999》设计的智能自动化工具&#…...

Win11Debloat系统优化工具:从问题诊断到长效维护的完整实践指南

Win11Debloat系统优化工具&#xff1a;从问题诊断到长效维护的完整实践指南 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本&#xff0c;用于从Windows中移除预装的无用软件&#xff0c;禁用遥测&#xff0c;从Windows搜索中移除Bing&#xff0c;以及执行各种其他更改…...

英雄联盟智能助手League Akari:5个必用功能让你的游戏体验翻倍提升

英雄联盟智能助手League Akari&#xff1a;5个必用功能让你的游戏体验翻倍提升 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit Le…...

华为光猫配置解密工具全解析:从加密破解到网络运维实战指南

华为光猫配置解密工具全解析&#xff1a;从加密破解到网络运维实战指南 【免费下载链接】HuaWei-Optical-Network-Terminal-Decoder 项目地址: https://gitcode.com/gh_mirrors/hu/HuaWei-Optical-Network-Terminal-Decoder 在网络运维工作中&#xff0c;光猫设备的配置…...