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

【代码随想录】算法训练营 第十五天 第六章 二叉树 Part 2

102. 二叉树的层序遍历

层序遍历,就是一层一层地遍历二叉树,最常见的就是从上到下,从左到右来遍历,遍历的方法依然有两种,第一种是借助队列,第二种则是递归,都算是很简单、很容易理解的方法,下面来分别介绍一下。

队列法

使用队列法讲究的就是一个简单粗暴,顺着做下去就行了。

首先要定义一个队列,这个队列的元素都得是二叉树结点,因为它是用来暂存二叉树的一层的。先是把根结点入队,当然如果连根结点都没有的话,就直接返回空数组了(要返回的是保存各层元素的二维数组,用vector容器实现);

接着就用vector定义一个保存遍历下来的元素的二维数组,作为result来最终返回答案;

现在就开始遍历了,我们用的是while循环,当队列为空时停止,在一轮循环中,队列存的是这层要遍历的结点,所以先定义一个size来保存未经遍历的层结点数,因为下面我们在遍历一个结点后就要把它出队,以便于存入下一层的结点;

遍历中,使用一个一维数组保存元素值,然后就把这个结点的左右子结点依次入队,因为是队列,就不用像栈那样反着来。每层遍历结束后,就把遍历得到的元素数组push进result二维数组里。

具体代码如下:

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> result;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

递归法

这个不用掌握,了解一下即可。但是下面的两道还是优先使用递归来做。

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth) {if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result,depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

226. 翻转二叉树

题目

思路

看到翻转,你可能会先想到一层一层地将结点翻转,但其实不用这么复杂,稍微观察一下就知道,只需要翻转每个结点的两个子结点即可,所以这里就可以用递归遍历的方法来做,先对调两个子结点,再遍历子结点,最后返回根结点即可。

盲区

随想录刷到这里才知道,swap函数还可以用来对调两个二叉树结点,长知识了:

swap(root->left, root->right);

代码

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);invertTree(root->left);invertTree(root->right);return root;}
};

101. 对称二叉树

题目

思路

还是用递归来做,每次递归判断对称的两个结点,若其中一个为空则返回false,两个都为空则返回true,接着都是不为空的,此时就判断两个结点值是否相等,不相等就返回false,否则就接着往下递归,先递归判断左边的左孩子和右边的右孩子,再递归判断左边的右孩子和右边的左孩子,这样就是对称位置的结点来判断是否相等了,将判断结果分别赋值给一个布尔变量,两个布尔变量都为true时就返回true。

代码

class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;else if (left->val != right->val) return false;bool outside = compare(left->left, right->right);bool inside = compare(left->right, right->left);bool isSame = outside && inside;return isSame;}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};

相关文章:

【代码随想录】算法训练营 第十五天 第六章 二叉树 Part 2

102. 二叉树的层序遍历 层序遍历&#xff0c;就是一层一层地遍历二叉树&#xff0c;最常见的就是从上到下&#xff0c;从左到右来遍历&#xff0c;遍历的方法依然有两种&#xff0c;第一种是借助队列&#xff0c;第二种则是递归&#xff0c;都算是很简单、很容易理解的方法&am…...

使用ssl_certificate_by_lua指令动态加载证书

1、下载 OpenResty - 下载 根据自己系统选择下载&#xff0c;我的是64位 2、解压到目录 3、启动openresty 进入解压后的目录&#xff0c;执行nginx.exe 浏览器输入 http://localhost 查看是否正常。显示以下画面就表示没有问题。 接下来可以开始准备动态安装证书 4、使用o…...

Qt中Opencv转Qimage出现重影或者颜色不对

废话不多说 在qt中opencv获取的图像转qimage时出现重影原因&#xff1a; 图像数据的内存对齐可能会导致画面重影&#xff0c;如果出现误差转换出来的图就会出现重影 解决办法&#xff1a; cv::Mat image_bgr cv::imread(“example.jpg”); cv::Mat image_aligned; cv::copyMak…...

upload-labs-1

文章目录 Pass-01 Pass-01 先上传一个正常的图片&#xff0c;查看返回结果&#xff0c;结果中带有文件上传路径&#xff0c;可以进行利用&#xff1a; 上传一个恶意的webshell&#xff0c;里面写入一句话木马&#xff1a; <?php eval($_POST[cmd]); echo "hello&quo…...

【vite配置路径别名@】/启动配置

npm install types/node --save-dev npm install path --save import { defineConfig } from vite import vue from vitejs/plugin-vue // 配置别名 import { resolve } from "path";// https://vitejs.dev/config/ export default defineConfig({plugins: [vue()]…...

3. List

数据结构在Java集合中的对应关系 线性表【数组】 -> ArrayList 线性表【链表】-> LinkedList 队列 -> Queue -> LinkedList&#xff0c;PriorityQueue, ArrayBlockingQueue … etc. 双端队列 -> Deque -> ArrayDeque 栈 -> LinkedList 哈希表 -> Hash…...

Django初窥门径-oauth登录认证

引言 在现代Web应用程序中&#xff0c;用户身份验证和授权是至关重要的组成部分。Django&#xff0c;一个流行的Python Web框架&#xff0c;为用户身份验证提供了内置支持。本文将探讨如何创建和注册Django应用&#xff0c;自定义身份验证服务&#xff0c;配置AUTHENTICATION_…...

数学到底在哪里支撑着编程?

数学到底在哪里支撑着编程&#xff1f; 除了少数算法等明显相关情况外&#xff0c;说点日常的。 编程是个极度依赖逻辑的领域&#xff0c;逻辑严谨性好&#xff0c;你的编程工作会顺畅很多一-绝大多 数的bug都是最近很多小伙伴找我&#xff0c;说想要一些嵌入式的资料&#x…...

Python模块ADB的, 已经 pyadb

Python模块ADB的使用指南_笔记大全_设计学院 (python100.com) pip install adb Python 调用ADB_python 调用adb命令_实相实相的博客-CSDN博客 Python ADB.shell_command Examples, pyadb.ADB.shell_command Python Examples - HotExamples Gitee 极速下载/PyADB - 码云 - 开…...

猫头虎分享从Python到JavaScript传参数:多面手的数据传递术

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

注解汇总:Spring 常用的注解

前言 本栏目的内容已经讲完了&#xff0c;本案例将把案例中所有讲到的注解都汇总起来&#xff0c;方便日后的学习需要用到的时候能够快速的找到相应的注解。本案例将结合小案例一起做汇总&#xff0c;也想丹玉是再复习一遍讲过用过的注解。 一、注解汇总 1、Component Reposi…...

合肥工业大学操作系统实验5

✅作者简介:CSDN内容合伙人、信息安全专业在校大学生🏆 🔥系列专栏 :hfut实验课设 📃新人博主 :欢迎点赞收藏关注,会回访! 💬舞台再大,你不上台,永远是个观众。平台再好,你不参与,永远是局外人。能力再大,你不行动,只能看别人成功!没有人会关心你付出过多少…...

基于SpringBoot+Vue的点餐管理系统

基于springbootvue的点餐平台网站系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatisVue工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 菜品详情 个人中心 订单 管理员界面 菜品管理 摘要 点餐管理系统是一种用…...

C# 继承,抽象,接口,泛型约束,扩展方法

文章目录 前言模拟需求场景模拟重复性高的需求初始类结构继承优化抽象类 需求1&#xff1a;打印CreateTime方法1&#xff1a;使用重载方法2&#xff1a;基类函数方法3&#xff1a;泛型约束方法3.1&#xff1a;普通泛型方法方法3.2&#xff1a;高级泛型约束&#xff0c;扩展方法…...

mysql的备份和恢复

备份&#xff1a;完全备份 增量备份 完全备份&#xff1a;将整个数据库完整的进行备份 增量备份&#xff1a;在完全备份的基础之上&#xff0c;对后续新增的内容进行备份 备份的需求 1、在生产环境中&#xff0c;数据的安全至关重要&#xff0c;任何数据的都可能产生非常严重…...

【机器学习3】有监督学习经典分类算法

1 支持向量机 在现实世界的机器学习领域&#xff0c; SVM涵盖了各个方面的知识&#xff0c; 也是面试题目中常见的基础模型。 SVM的分类结果仅依赖于支持向量&#xff0c;对于任意线性可分的两组点&#xff0c;它 们在SVM分类的超平面上的投影都是线性不可分的。 2逻辑回归 …...

lv11 嵌入式开发 计算机硬件基础 1

目录 1 导学 1.1回顾及导学 1.2 嵌入式系统分层 1.3 linux底层开发 2 ARM体系结构与接口技术课程导学 3 计算机基础 3.1 计算机的进制 3.2 计算机组成 3.3 总线 4 多级存储结构与地址空间 4.1 多级存储概念 4.2 地址空间 5 CPU工作原理 6 练习 1 导学 1.1回顾及导…...

【Linux】vim

文章目录 一、vim是什么&#xff1f;二 、命令模式三、插入模式四、底行模式五、vim配置 一、vim是什么&#xff1f; Vim是一个强大的文本编辑器&#xff0c;它是Vi的增强版&#xff0c;支持多种语法高亮、插件扩展、多模式操作等功能。Vim有三种基本的工作模式&#xff1a;命…...

cstring函数

string 1.char str[]类型 fgets(s,10000,stdin) cin.getline(cin,10000) strlen(str) sizeof 求静态数组长度 2.string类型 getline(cin,a) cin.getline(cin,10000) str.lenth() str.size() cin 遇到空格就停止 3.gets 函数 char str[20]; gets(str); 4.puts 函…...

【owt】p2p client mfc 工程梳理

1年前构建的,已经搞不清楚了。所以梳理下,争取能用较新的webrtc版本做测试。最早肯定用这个测试跑通过 【owt】p2p Signaling Server 运行、与OWT-P2P-MFC 交互过程及信令分析官方的mfc客户端 估计是构造了多个不同的webrc版本的客户端...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...