随想录二刷Day15——二叉树
文章目录
- 二叉树
- 2. 递归遍历二叉树
- 3. 二叉树的迭代遍历
- 4. 二叉树的统一迭代法
二叉树
2. 递归遍历二叉树
144. 二叉树的前序遍历
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;preorder(root, result);return result;}private:void preorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;result.push_back(root->val);preorder(root->left, result);preorder(root->right, result);}
};
94. 二叉树的中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;inorder(root, result);return result;}private:void inorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;inorder(root->left, result);result.push_back(root->val);inorder(root->right, result);}
};
145. 二叉树的后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;postorder(root, result);return result;}private:void postorder(TreeNode *root, vector<int> &result) {if (root == NULL) return ;postorder(root->left, result);postorder(root->right, result);result.push_back(root->val);}
};
3. 二叉树的迭代遍历
144. 二叉树的前序遍历
遍历顺序:中左右
压栈顺序:中(直接弹出)右左
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左}return result;}
};
145. 二叉树的后序遍历
先序遍历:中左右
后序遍历:左右中
所以把先序遍历的压栈顺序修改,得到遍历 中右左 的顺序,然后翻转遍历结果。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;if (root == NULL) return result;stack<TreeNode *> stk;stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();result.push_back(cur->val); // 中if (cur->left) stk.push(cur->left); // 左if (cur->right) stk.push(cur->right); // 右}reverse(result.begin(), result.end()); // 此时遍历顺序为 中右左,翻转得到后序遍历的结果return result;}
};
94. 二叉树的中序遍历
中序遍历不太一样,要借助指针查看左子节点是否为空,来得到左中右的遍历结果
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;TreeNode *cur = root;while ( cur != NULL || !stk.empty() ) {if (cur != NULL) { // 如果当前节点不空,则一直找左子节点stk.push(cur);cur = cur->left;} else {cur = stk.top(); // 上个节点的左节点已经找完了stk.pop();result.push_back(cur->val); // 左完了该中cur = cur->right; // 中完了去看右子树}}return result;}
};
4. 二叉树的统一迭代法
统一遍历方式,按遍历顺序的逆序输出结果。
144. 二叉树的前序遍历
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) { // 遇到 null 说明是待处理节点if (cur->right) stk.push(cur->right); // 右if (cur->left) stk.push(cur->left); // 左stk.push(cur); // 中stk.push(NULL); // 标记节点} else { // 遇到 NULL 标记,开始处理节点cur = stk.top(); // 取出被标记的待处理节点result.push_back(cur->val);stk.pop();}}return result;}
};
94. 二叉树的中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) {if (cur->right) stk.push(cur->right); // 右stk.push(cur); // 中stk.push(NULL); // 标记if (cur->left) stk.push(cur->left); // 左} else {cur = stk.top();result.push_back(cur->val);stk.pop();}}return result;}
};
145. 二叉树的后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> stk;if (root) stk.push(root);while ( !stk.empty() ) {TreeNode *cur = stk.top();stk.pop();if (cur) {stk.push(cur);stk.push(NULL);if (cur->right) stk.push(cur->right);if (cur->left) stk.push(cur->left); } else {cur = stk.top();result.push_back(cur->val);stk.pop();}}return result;}
};
相关文章:
随想录二刷Day15——二叉树
文章目录二叉树2. 递归遍历二叉树3. 二叉树的迭代遍历4. 二叉树的统一迭代法二叉树 2. 递归遍历二叉树 144. 二叉树的前序遍历 class Solution { public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;preorder(root, result);return res…...
docker-compose部署kafka服务时如何同时允许内外网访问?
背景 最近在学习kafka相关知识,需要搭建自己的kafka环境。综合考虑后决定使用docker-compose来管理维护这个环境。 docker-compose.yml Bitnami的yml文件就很不错,这里直接拿来用了。 version: "2"services:zookeeper:image: docker.io/bi…...
数据结构刷题(二十):17电话号码的字母组合、39组合总和、40组合总和II
一、电话号码的字母组合题目链接思路:回溯三部曲。确定回溯函数参数:题目中给的 digits,还要有一个参数就是int型的index(记录遍历第几个数字,就是用来遍历digits的,同时也代表了递归的深度)&am…...
Java面试总结(五)
sleep() 方法和 wait() 方法对比 相同点 两者都可以暂停线程的执行;两者都可以响应中断。 不同点 sleep()方法不会释放锁,wait()方法会释放锁; sleep()方法主要用于暂停线程的执行,wait()方法主要用于线程之间的交互/通信&…...
三维人脸实践:基于Face3D的渲染、生成与重构 <二>
face3d: Python tools for processing 3D face git code: https://github.com/yfeng95/face3d paper list: PaperWithCode 3DMM方法,基于平均人脸模型,可广泛用于基于关键点的人脸生成、位姿检测以及渲染等,能够快速实现人脸建模与渲染。推…...
在linux上部署Java项目
在Linux部署Java环境 要是想要部署java web程序,首先要配置环境 jdk tomcat mysql 安装jdk 推荐的方法是使用yum直接安装openjdk(开源的,与官方的jdk功能差不多),目前使用的最多的就是jdk8系列 yum list | grep jdk 在源上搜索所有关于jdk的文件 devel表示development的意思…...
线性表的接口
线性表的实现方式 顺序表 顺序表是一种线性表的实现方式,它是用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理上也相邻⁴。顺序表可以用数组来实现,它的优点是可以快速定位第几个元素,但是缺点…...
spark三种操作模式的不同点分析
通常情况下,由于mapreduce计算引擎的效率问题,大部分公司使用的基本都是hive数仓spark计算引擎的方式搭建集群,所以对于spark的三种操作方式来进行简单的分析。在日常开发中,使用最多的方式取决于具体的需求和场景。以下是每种方式的一些常见用途:Spark …...
Vue3做出B站【bilibili】 Vue3+TypeScript【快速入门一篇文章精通系列(一)前端项目案例】
本项目分为二部分 1、后台管理系统(用户管理,角色管理,视频管理等) 2、客户端(登录注册、发布视频) Vue3做出B站【bilibili】 Vue3TypeScript【快速入门一篇文章精通系列(一)前端项目…...
猜数游戏--课后程序(Python程序开发案例教程-黑马程序员编著-第3章-课后作业)
实例10:猜数游戏 猜数游戏是一个古老的密码破译类、益智类小游戏,通常由两个人参与,一个人设置一个数字,一个人猜数字,当猜数字的人说出一个数字,由出数字的人告知是否猜中:若猜测的数字大于设…...
Nvidia jetson nano 部署yolov5_技术文档
Nvidia jetson nano 部署yolov5_技术文档 每天一句小姜格言:我行,我不是一般人儿 部署开始: 1、通过FileZilla,将window文件传输至jetson nano 上的nano文件夹下。 2、查看cuda 我买的jetson nano是带有配置好的镜像。系统配置…...
获取当前天数前N天
获取当前天数前N天 先封装到js里面 export const isTime (val) > {// 1.获取当前时间年月日时分秒格式xxxx-xx-xx xx:xx:xxvar myDate new Date() // 当前时间var y myDate.getFullYear() // 当前年份四位数var m myDate.getMonth() 1 < 10? 0 (myDate.getMont…...
Linux---基本指令
专栏:Linux 个人主页:HaiFan. 基本指令ls 指令pwd命令cd 指令touch指令mkdir指令(重要)rmdir指令 && rm 指令(重要)man指令(重要)cp指令(重要)mv指令…...
【UE4 RTS游戏】02-摄像机运动_完成摄像机在X轴上运动的相关步骤
效果通过控制键盘WS键使得“CameraPawn”进行前后移动步骤将landscape的Z轴位置更改为0删除“PostProcessVolume”将“LightmassImportanceVolume”移入Lighting文件夹内新建一个蓝图类,父类是Pawn,命名为“CameraPawn”将“MyController”重命名为“Cam…...
Kubernetes学习(五)持久化存储
Volume 卷 容器中的文件在磁盘上是临时存放的,这给容器中运行的特殊应用带来了一些问题。首先,当容器崩溃时,kubectl将重新启动容器,容器中的文件将会丢失--应为容器会以干净的状态重建。其次,当在一个Pod中运行多个容…...
下一个7年,保持期待、持续思考,酷雷曼继续向前!
过去7年,我们一直在思考, VR技术究竟能为我们的生活带来什么? 是足不出户就能云游千里的秀美风光? 是在家就能沉浸式体验线上消费的便利? 还是为商企和用户搭建更快速的沟通桥梁? NO.1、技术变革 在信…...
天梯赛训练L1-010--L1-012
目录 1、L1-010 比较大小 2、L1-011 A-B 3、L1-012 计算指数 4,一些题外话 1、L1-010 比较大小 分数 10 本题要求将输入的任意3个整数从小到大输出。 输入格式: 输入在一行中给出3个整数,其间以空格分隔。 输出格式: 在一…...
三分钟完成Stable Diffusion本地安装(零基础体验AI绘画)
三分钟完成Stable Diffusion本地安装前言安装步骤下载链接前言 最近AI绘画很火,很多无编程基础的小伙伴也想体验一下,所以写这篇博客来帮助小伙伴们愉快的体验一下~废话少说,我们直接开整! 安装步骤 首先,下载本项目的…...
电子台账:教程目录及软件下载
前面内容有点杂乱,这里整理一下教程目录。重点是制作模板,企业只要学会适合自己的一种就行。如果这些模板都学会做了,那可以当老师了。1 目录1 模板制作之一——列过滤(水平过滤)2 模板制作之二——行过滤(…...
多态的优势和弊端
目录 1.多态的优势 2.多态的弊端是什么? 3.引用数据类型的类型,转换有几种方式 4.强制类型转换能解决什么问题楠? 1.多态的优势 方法中,使用父类作为参数,可以接收所有子类的对象 package ploydemo3;import java.u…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
