代码随想录阅读笔记-二叉树【统一迭代法】

此前我们用递归的方式,实现了二叉树前中后序的遍历,又用栈实现了二叉树前后中序的迭代遍历(非递归)。之后我们发现迭代法实现的先中后序,其实风格也不是那么统一,除了先序和后序,有关联,中序完全就是另一个风格了,一会用栈遍历,一会又用指针来遍历。

其实针对三种遍历方式,使用迭代法是可以写出统一风格的代码!

我们以中序遍历为例,在上一篇文章中提到说使用栈的话,无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况

那我们就将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。

如何标记呢,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

迭代法中序遍历

中序遍历代码如下:(详细注释)

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中if (node->right) st.push(node->right);  // 添加右节点(空节点不入栈)st.push(node);                          // 添加中节点st.push(NULL); // 中节点访问过,但是还没有处理,加入空节点做为标记。if (node->left) st.push(node->left);    // 添加左节点(空节点不入栈)} else { // 只有遇到空节点的时候,才将下一个节点放进结果集st.pop();           // 将空节点弹出node = st.top();    // 重新取出栈中元素st.pop();result.push_back(node->val); // 加入到结果集}}return result;}
};

看代码有点抽象我们来看一下动画(中序遍历):

中序遍历迭代(统一写法)

动画中,result数组就是最终结果集。

可以看出我们将访问的节点直接加入到栈中,但如果是处理的节点则后面放入一个空节点, 这样只有空节点弹出的时候,才将下一个节点放进结果集。

此时我们再来看前序遍历代码。

迭代法前序遍历

迭代法前序遍历代码如下: (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right);  // 右if (node->left) st.push(node->left);    // 左st.push(node);                          // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

迭代法后序遍历

后续遍历代码如下: (注意此时我们和中序遍历相比仅仅改变了两行代码的顺序)

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();st.push(node);                          // 中st.push(NULL);if (node->right) st.push(node->right);  // 右if (node->left) st.push(node->left);    // 左} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/287599.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Redis如何应对缓存穿透问题——Java全栈知识(9)

我们在正常使用缓存的时候的流程大概就是这样的&#xff1a; 请求访问缓存&#xff0c;缓存有数据就返回&#xff0c;缓存无数据就去数据库里面查数据写入到缓存中。 1、缓存穿透问题 但是如果由恶意请求&#xff0c;短时间内大量的访问不存在的数据&#xff0c;这时每个请求…

数据结构

一、栈 先进后出 二、队列 先进先出 三、数组 查询快&#xff0c;增加修改慢 四、链表 查询慢&#xff0c;增加修改慢 五、二叉树 节点&#xff1a; 查找二叉树 二叉查找树的特点 二叉查找树,又称二叉排序树或者二叉搜索树 每一个节点上最多有两个子节点 左子树上所…

算法---动态规划练习-5(下降路径最小和)

下降路径最小和 1. 题目解析2. 讲解算法原理方法一方法二 3. 编写代码法一法二 1. 题目解析 题目地址&#xff1a;点这里 2. 讲解算法原理 方法一 首先&#xff0c;通过matrix的大小确定矩阵的行数m和列数n。 创建一个大小为(m1) (n2)的二维动态规划数组dp&#xff0c;其中d…

就业班 第二阶段 2401--3.26 day6 Shell初识 连接vscode

远程连接vs_code可能出现的问题 C:\Users\41703\.ssh 验证远程主机的身份&#xff0c;如果连不上vscode&#xff0c;可以尝试删除这里面的公钥代码。 重新安装那个扩展&#xff0c;排除扩展本身的问题 谁连过我&#xff0c;并操作了什么 curl https://gitea.beyourself.org.c…

Django路由

Router介绍 在实际开发过程中&#xff0c;一个Django项目会包含很多的app,这时候如果我们只在主路由里进行配置就会显得杂乱无章&#xff0c;所以通常会在每个app里&#xff0c;创建各自的urls.py路由模块&#xff0c;然后从根路由出发&#xff0c;将app所属的url请求&#xff…

Spring Boot | Spring Boot的“核心配置“与“注解“

目录: Spring Boot的核心配置与注解 &#xff1a;1. 全局配置文件 ( application.properties / application.yaml&#xff1a;创建项目时候自动生成&#xff0c;其会被“自动导入”到“程序”中 )application.properties配置文件application.yaml 配置文件 (推荐使用)当value值…

PSA制氧装置的工作原理及应用解析

PSA制氧装置&#xff0c;即变压吸附制氧装置&#xff0c;是一种广泛应用于工业生产与其他领域的重要设备。该装置基于吸附剂在不同压力下对气体分子吸附能力的差异&#xff0c;通过周期性压力变化来实现氧气的分离与提纯。 工作原理 PSA制氧装置的工作原理主要基于物理吸附与解…

【ESP32S3 Sense接入百度在线语音识别】

视频地址&#xff1a; ESP32S3 Sense接入百度在线语音识别 1. 前言 使用Seeed XIAO ESP32S3 Sense开发板接入百度智能云实现在线语音识别。自带麦克风模块用做语音输入&#xff0c;通过串口发送字符“1”来控制数据的采集和上传。 步骤概括    (1) 在百度云控制端选择“语音…

JVM(三)——字节码技术

三、字节码技术 1、类文件结构 一个简单的 HelloWorld.java package com.mysite.jvm.t5; // HelloWorld 示例 public class HelloWorld {public static void main(String[] args) {System.out.println("hello world");} }执行 javac -parameters -d . HellowWorld.…

会员中心微服务

文章目录 1.环境配置1.创建会员中心模块2.检查父子模块的pom.xml1.父模块注意&#xff1a;如果父模块中的依赖显示not found&#xff0c;原因是子模块并没有引用&#xff0c;不用在意 2.子模块 3.pom.xml 引入相关依赖&#xff08;别忘记刷新maven&#xff09;4.application.ym…

机器学习预测气候变化对产量的影响

通过机器学习预测作物产量 今天分享一篇文献解读&#xff0c;将围绕论文《结合机器学习和环境变量约束气候变化下作物产量变化预测的不确定性》展开,该研究通过将动态线性模型(DLM)和随机森林机器学习模型(RF)分别与9个全球网格作物模型(GGCM)集成来整合和克服这两种建模框架的…

webpack练习之手写loader

手写一个style-loader来把样式文件插入head里面&#xff0c;准备工作 vue webpack就自己弄了&#xff0c;webpack的一些配置也自己配置好 一、创建index.css文件 .box{width: 100px;height: 100px;background-color: red; }然后在vue的main.js文件中引入它 二、创建自定义l…

jmeter二次开发发送java请求_保姆级教程!!!

一、引言 JMeter是Apache基金会开发的一款开源性能测试工具,广泛应用于软件性能测试领域。它能够模拟多线程并发用户对应用程序进行压力测试,以评估应用程序的性能和稳定性。然而,在实际使用过程中,用户可能会遇到需要发送Java请求的场景,例如测试Java Web应用程序或其他…

【Monero】Wallet RPC | Wallet CLI | 门罗币命令行查询余额、种子、地址等命令方法教程

ubuntu22.04 首先在运行daemon&#xff0c;详细安装运行教程可参考&#xff1a;The Monero daemon (monerod) ./monerodWallet CLI run ./monero-wallet-cli如果还没有钱包就根据提示创建钱包即可 输入密码 查询余额 balance查询种子 seed其他可执行命令操作&#xff1…

拌合楼管理软件开发(十一) 海康威视车牌识别摄像头安装调试,总算是跑通了。

前言&#xff1a;总算是调测通了 话接上回&#xff0c;车牌识别摄像头买回来了&#xff0c;卡在电源上了&#xff0c;今天抽时间把电源问题解决了&#xff0c;开始代码正式的调测。一切还算顺利了&#xff0c;没有再碰到打脸的事情了。 一、电源接线&#xff1a; 如同前面预想的…

selenium元素定位--xpath定位--层级与逻辑组合定位

其他元素非唯一时&#xff0c;又不想用xpath绝对定位时&#xff0c;需要用到层级与逻辑定位. 一、层级属性结合定位&#xff1a; 遇到元素没有class、name、id等或属性动态变化情况时&#xff0c;可以找父节点元素&#xff0c;父级节点没有id时&#xff0c;可以继续往上找id&…

linux在使用重定向写入文件时(使用标准C库函数时)使处理信号异常(延时)--问题分析

linux在使用重定向写入文件时(使用标准C库函数时)使处理信号异常(延时)–问题分析 在使用alarm函数进行序号处理测试的时候发现如果把输出重定向到文件里面会导致信号的处理出现严重的延迟(ubuntu18) #include <stdio.h> #include <stdlib.h> #include <unist…

UE5 C++ 3D血条 响应人物受伤 案例

一.3Dwidget 1.创建C Userwidget的 MyHealthWidget&#xff0c;声明当前血量和最大血量 UCLASS() class PRACTICEC_API UMyHealthWidget : public UUserWidget {GENERATED_BODY() public:UPROPERTY(EditAnywhere,BlueprintReadWrite,Category "MyWidget")float C…

Ubuntu连不上外网的问题—ping不通baidu.com

一、问题 虚拟机不能联网&#xff0c;ping百度时候出现这个问题 book100ask:~$ ping www.baidu.com ping: www.baidu.com: Name or service not known 二、解决办法 首先&#xff0c;定位问题&#xff0c;再问我出现的问题中&#xff0c;认为是NAT设置的问题&#xff0c;只要…

【Frida】【Android】02_JAVA层HOOK

&#x1f6eb; 系列文章导航 【Frida】【Android】01_手把手教你环境搭建 https://blog.csdn.net/kinghzking/article/details/136986950【Frida】【Android】02_JAVA层HOOK https://blog.csdn.net/kinghzking/article/details/137008446【Frida】【Android】03_RPC https://bl…