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

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

94.二叉树的中序遍历

2、题目描述

二、个人思路整理

1、思路分析

递归解法（空间复杂度O(n) 、时间复杂度O(n)）

1. 递归终止条件：当前节点为空，则直接返回；
2. 递归体：

• 先递归遍历左子树；
• 访问根节点；
• 再递归遍历右子树。

迭代解法（空间复杂度O(n)、时间复杂度O(n)）

迭代解法即利用显式栈来模拟系统栈的递归行为。

1. 创建栈和一个遍历指针；
2. 遍历指针一直向左，将左节点依次入栈，到达最左边（没有左孩子）时（说明此节点是叶子节点（或根节点）），弹栈并记录结果；
3. 处理完左边，弹栈记录完根节点（或叶子节点）后，处理右子树。

（我的理解是先把左边（左节点）都入栈，然后到达最左端后，依次一层一层往上返，处理每一层的右子树（右节点），当然右子树也可能存在左节点，依次循环这样遍历即可，每当没有左孩子时，说明此节点是根节点（或叶子节点），记录到结果中即可）

下面为大模型相关解释（防遗忘）

迭代过程就是：一路向左推入栈，无路可走弹栈输出，然后向右迈一步。

• 栈的作用：暂存父节点，方便在左子树处理完后能够“回溯”回来访问根节点和右子树。

拆解为 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,vector<int>&res){if(!root){return;}inorder(root->left,res);//左res.push_back(root->val);//根inorder(root->right,res);//右}vector<int>inorderTraversal(TreeNode*root){vector<int>res;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:vector<int>inorderTraversal(TreeNode*root){vector<int>res;stack<TreeNode*>st;TreeNode*cur=root;while(cur!=nullptr||!st.empty()){//1. 一直向左，将所有左节点入栈while(cur!=nullptr){st.push(cur);cur=cur->left;//左}//2. 当没有左孩子，即到达最左边时，弹出栈顶元素cur=st.top();st.pop();res.push_back(cur->val);//中//3. 根节点处理完，转向处理右子树cur=cur->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 nlog2​n，调用栈最多同时保存log ⁡ 2 n \log_2 nlog2​n层函数，空间复杂度为O ( log ⁡ n ) O(\log n)O(logn)）；最坏情况（单链树，二叉树退化成一条链，调用栈的最大深度达到n nn，空间复杂度为O ( n ) O(n)O(n)）。