LeetCode94. 二叉树的中序遍历(递归与非递归)

news/2024/10/23 5:49:56/

写在前面:

题目链接:添加链接描述
编程语言:c++
题目难度:简单

一、题目描述

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。
在这里插入图片描述

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

二、解题思路

2.1 递归

先来念一下我们的 中序遍历口诀 " 左根右 " “左根右”
对于二叉树的遍历方法基本概念不太了解的可以参考下面的博客:
二叉树的前序/中序/后序遍历新手入门介绍
言归正传:
在这里插入图片描述
递归的代码实现:

class Solution {
public:void LDR(TreeNode* root, vector<int>& vctResult){if(root == nullptr){return;}LDR(root->left, vctResult);vctResult.push_back(root->val);LDR(root->right, vctResult);}vector<int> inorderTraversal(TreeNode* root) {vector<int> vctResult;LDR(root, vctResult);return vctResult;}
};

我们结合代码和图示进行讲解思路:
首先一直往左孩子遍历,直到找到了叶子节点,然后将 该节点 值保存

在这里插入图片描述
接下来继续遍历 4 的 right 4 的 右孩子也为 空,4 的左右子树遍历结束; 再次 return 返回上一层 即 根节点 为 2 ,并保存该节点值,节点 2 的 左子树已经遍历完毕,接下来遍历 2 的右孩子

结合逻辑,我们再看一下代码的调用关系:
在这里插入图片描述
递归中序遍历运行结果:
在这里插入图片描述

2.2 非递归

非递归的中序遍历我们需要借助一个 栈来辅助我们遍历
中序遍历,第一个是要找 最左的孩子,那么我们就从根开始往左孩子遍历,依次将左孩子入栈,那么,最后一个入栈的,也就是栈顶元素就是最左边的孩子节点
在这里插入图片描述

代码:

            while(root != nullptr){staTemp.push(root);root = root->left;}root = staTemp.top();//取栈顶元素staTemp.pop();vctResult.push_back(root->val);//存值

判断完 2 的 左孩子为 nullptr 后,那么意味着 2 没有 左,按照 左根右的顺序,2 将作为 根 节点 值进行保存,接下俩,按照左根右的顺序,继续遍历 2 的右孩子,若 2 的右孩子不为 nullptr 则继续入栈
即:

root = root->right; //遍历右孩子

2 的 右孩子依然为 nullptr,此时栈里还剩元素 1
在这里插入图片描述
代表 1 的左子树已经遍历结束,接下来继续遍历 1 的 右孩子,并将 1 pop 出去,保存 1 的值
并继续遍历 该节点 1 的右孩子

并继续将 3 入栈,并继续遍历 节点 3 的左孩子节点
在这里插入图片描述

左孩子为 nullptr 此时栈顶元素 为 3 ,将 3 值保存 并 pop 出去,并继续遍历 3 的右孩子,3 的右孩子为 nullptr 栈为 空 且 所有节点遍历结束,那么整个中序遍历也已结束。
完整代码示例:

        vector<int> vctResult;  //中序遍历非递归写法stack<TreeNode*> staTemp;while(root != nullptr || !staTemp.empty()) {while(root != nullptr){staTemp.push(root);root = root->left;//遍历左孩子}root = staTemp.top();//取栈顶元素 staTemp.pop();//值取过就 pop出去vctResult.push_back(root->val);root = root->right;//继续遍历右孩子}return vctResult;

运行结果:

在这里插入图片描述


http://www.ppmy.cn/news/75268.html

相关文章

使用Amazon EC2实例部署三个项目

在部署这三个项目时&#xff0c;以下是一种可能的思路&#xff1a; 1. **配置服务器环境&#xff1a;**确保你的服务器已经安装了适当的操作系统&#xff08;例如Linux&#xff09;和所需的软件&#xff08;如Python、Node.js等&#xff09;。 2. **设置域名和端口&#xff1a;…

【图论】想越狱的小衫

题目描述 这次小杉来到了经典美剧《越狱》的场景里……他被抓起来了&#xff08;-.-干嘛幻想这么郁闷的场景……&#xff09;。 小杉身为新一代的Scofield&#xff0c;在挖了半个月之后终于挖通牢房里的地道。 在地道里&#xff0c;无数的管道路线困惑了他。 小杉看了看自己…

游戏洞察丨自来水还是井水,后流量时代的私域挑战

流量生意本质上是买卖用户浏览时间的生意&#xff0c;如果用户增长到顶&#xff0c;那就意味着供给到顶。对比 2021 年&#xff0c;2022 年的游戏出海在谷歌和 Facebook 上投入的广告成本几乎翻了一倍。新晋“渠道王者”TikTok 逐渐走进大家的视野。该现象背后的原因在于&#…

MySQL数据库最常见的6种故障的排除方法

MySQL数据库最常见的6中故障的排除方法 1.MySQL无法启动 2.MySQL连接不上 3.MySQL打开文件失败 4.MySQL挂起&#xff08;hung&#xff09; 5.MySQL崩溃&#xff08;crash&#xff09; 6.忘记用户密码 1.MySQL无法启动 1.无法访问系统资源 2.参数设置错误 无法访问系统…

ffmpeg命令行工具源码之结构体分析1-命令行参数(未完结,持续更新)

前言 ffmpeg作为多媒体文件转换工具&#xff0c;至少需要有一个要转换的输入文件信息&#xff08;不仅仅是普通文件&#xff0c;还可以是摄像头设备&#xff0c;网络流等&#xff09;&#xff0c;和通常至少需要一个输出格式的文件&#xff08;输出文件不仅仅指普通的文件&…

【SQL】MySQL的数据类型

MySQL的数据类型 MySQL是一种广泛使用的关系型数据库管理系统&#xff0c;它支持各种数据类型&#xff0c;包括数字、字符串、日期和时间等。在MySQL中&#xff0c;数据类型是用来定义表中列的类型&#xff0c;它决定了表中的数据如何被存储和操作。 数字类型 MySQL支持多种…

完犊子!原单位的离职证明丢了,下周要入职了,用AI做一个行不行?

弄丢了离职证明怎么办&#xff1f; 一位网友哀叹&#xff1a; 完犊子&#xff01;原单位的离职证明丢了&#xff0c;下周要入职了&#xff0c;现在怎么办&#xff1f;用AI做一个行不行&#xff1f; 有相同经历的网友安慰他&#xff0c;离职证明没了没事&#xff0c;新公司会要求…

格式化数据写入sprintf的用法

sprintf 是一个常见的 C 语言函数&#xff0c;用于将格式化的数据写入字符串缓冲区中。它的原型如下&#xff1a; int sprintf(char *str, const char *format, …); sprintf 函数将按照指定的格式 format 将数据写入字符串 str 中&#xff0c;并返回写入的字符数&#xff08;不…