【二叉树】LC 94.二叉树的中序遍历-北京尧图网络

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析递归解法空间复杂度O(n) 、时间复杂度O(n)迭代解法空间复杂度O(n)、时间复杂度O(n)2、解题代码递归解法空间复杂度O(n) 、时间复杂度O(n)迭代解法空间复杂度O(n)、时间复杂度O(n)三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接94.二叉树的中序遍历2、题目描述二、个人思路整理1、思路分析递归解法空间复杂度O(n) 、时间复杂度O(n)递归终止条件当前节点为空则直接返回递归体先递归遍历左子树访问根节点再递归遍历右子树。迭代解法空间复杂度O(n)、时间复杂度O(n)迭代解法即利用显式栈来模拟系统栈的递归行为。创建栈和一个遍历指针遍历指针一直向左将左节点依次入栈到达最左边没有左孩子时说明此节点是叶子节点或根节点弹栈并记录结果处理完左边弹栈记录完根节点或叶子节点后处理右子树。我的理解是先把左边左节点都入栈然后到达最左端后依次一层一层往上返处理每一层的右子树右节点当然右子树也可能存在左节点依次循环这样遍历即可每当没有左孩子时说明此节点是根节点或叶子节点记录到结果中即可下面为大模型相关解释防遗忘迭代过程就是一路向左推入栈无路可走弹栈输出然后向右迈一步。栈的作用暂存父节点方便在左子树处理完后能够“回溯”回来访问根节点和右子树。拆解为 3 个步骤往左走到底入栈指针不断往左孩子走沿途经过的所有节点都压入栈中保存因为左子树还没处理完当前节点还不能输出。弹栈输出访问“根”走到nullptr说明没有左孩子了时从栈中弹出一个节点。这就是当前子树最左边的节点或根节点记录它的值。往右迈一步转向右子树处理完当前节点后指针转向它的右孩子回到步骤 1继续重复对右子树执行相同的逻辑。为什么外层while需要cur ! nullptr || !st.empty()两个条件st.empty()为假栈不空时说明虽然当前节点走到了nullptr但栈里还压着之前的父节点需要弹出继续处理。cur ! nullptr为真时发生在刚转向右子树cur cur-right之后。此时栈可能恰好被弹空了比如刚处理完根节点但右子树里还有节点需要遍历必须靠cur ! nullptr才能进入循环继续压栈。2、解题代码递归解法空间复杂度O(n) 、时间复杂度O(n)/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:voidinorder(TreeNode*root,vectorintres){if(!root){return;}inorder(root-left,res);//左res.push_back(root-val);//根inorder(root-right,res);//右}vectorintinorderTraversal(TreeNode*root){vectorintres;inorder(root,res);returnres;}};迭代解法空间复杂度O(n)、时间复杂度O(n)/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintres;stackTreeNode*st;TreeNode*curroot;while(cur!nullptr||!st.empty()){//1. 一直向左将所有左节点入栈while(cur!nullptr){st.push(cur);curcur-left;//左}//2. 当没有左孩子即到达最左边时弹出栈顶元素curst.top();st.pop();res.push_back(cur-val);//中//3. 根节点处理完转向处理右子树curcur-right;//右}returnres;}};三、知识风暴中序遍历中序遍历是二叉树深度优先搜索DFS的一种常见方式其遍历规则为左子树-根节点-右子树。该算法时间复杂度与空间复杂度计算时间复杂度O ( n ) O(n)O(n)n为二叉树的节点总数每个节点进入inorder函数后执行的操作为O ( 1 ) O(1)O(1)总耗时为n × O ( 1 ) O ( n ) n \times O(1) O(n)n×O(1)O(n)。空间复杂度O ( n ) O(n)O(n)空间复杂度取决递归调用栈的最大深度。最好/平均情况平衡二叉树树高log ⁡ 2 n \log_2 nlog2n调用栈最多同时保存log ⁡ 2 n \log_2 nlog2n层函数空间复杂度为O ( log ⁡ n ) O(\log n)O(logn)最坏情况单链树二叉树退化成一条链调用栈的最大深度达到n nn空间复杂度为O ( n ) O(n)O(n)。

【二叉树】LC 94.二叉树的中序遍历

相关推荐

题解：洛谷 P1720 月落乌啼算钱（斐波那契数列）

记录一个需求，多行输入框 #变色输入话题，特殊符号，空格结束变色，且支持话题文字修改和删除，复制粘贴，限长500字，超出提示

DS4Windows完整指南：5分钟让PS手柄在Windows上畅玩所有游戏

更多资讯

ESP32-CAM图像传输全攻略：硬件接线、源码解析与Python接收端

Python校园一卡通消费行为分析：从数据清洗到可视化全流程实战

Vue集成海康威视H5player播放器：WebAssembly视频监控实战指南

ResNet+Transformer双引擎实现手写数学公式识别全解析

大数据挖掘工程实战：从架构设计到网约车项目落地

深入scriptc事件循环：kqueue与epoll跨平台实现的对比分析

今日更新

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？