二叉树的中序遍历
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个二叉树的根节点 root，返回它的 中序 遍历结果。
中序遍历顺序为：左子树 → 根节点 → 右子树。
示例 1
说明：先走到最左 1，再访问根 3（在节点 2 的左子树），最后 2。
示例 2
示例 3
模拟答题者思考
1. 我先写「定义式」暴力：中序就是 inorder(left) + [root.val] + inorder(right)，空树返回空——逻辑完全正确，一行递归就能过。
2. 重复在哪里？递归隐式用系统栈保存「还没访问的根、还没走的右子树」；题目进阶要求迭代，就是把这条调用栈显式模拟出来。
3. 迭代直觉：中序里任意节点，都要先把它左边整条链走完才能输出它——所以先一路向左，把路径上的节点压栈；左尽头时弹出栈顶（这就是下一个要输出的），再转去它的右子树重复。
4. 例 [1,null,2,3]：从 1 压栈；弹出 1 输出；cur=2，压 2、再压 3；弹出 3 输出；弹出 2 输出 → [1,3,2]。
5. 每个节点入栈、出栈各一次，时间 O(n)；栈深度最坏 O(n)（链状树）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
ans | list<int> | 定义：按中序收集的节点值序列 维护：每「真正访问」一个节点时追加其 val（左子树已全部处理完毕之后）更新：从栈弹出节点或递归到根时 append |
stk | stack<TreeNode*> | 定义：尚未完成中序的节点（其左链已下探、等待回溯后访问） 维护：栈顶是「下一个要被访问（输出）的节点」 更新：沿左子树一路 push；左无路可走时 pop 并输出，再转向右子树 |
cur | TreeNode* | 定义：当前正在下探或刚处理完的节点指针 维护： cur 非空时只负责向左深入；弹出栈顶后 cur = cur.right 继续中序右半段更新：初始 root；内层 while cur 中 cur = cur.left；每次弹出后 cur = 弹出节点.right |
落码步骤
1. 初始化 ans = []、stk = []、cur = root
2. 当 cur 非空或栈非空时循环：
3. 内层 while cur：将 cur 压栈，cur = cur.left（一路向左）
4. cur = stk.pop()，ans.append(cur.val)（访问根）
5. cur = cur.right（转向右子树，继续中序）
6. 返回 ans（递归写法：先左、再记值、再右，见代码注释）
代码实现
class Solution:
def inorderTraversal(self, root: TreeNode | None) -> list[int]:
ans: list[int] = []
stk: list[TreeNode] = []
cur = root
while cur or stk:
while cur:
stk.append(cur)
cur = cur.left
cur = stk.pop()
ans.append(cur.val)
cur = cur.right
return ans
# 递归版（思路对照，面试可先写再改迭代）：
# def inorder(node):
# if not node: return
# inorder(node.left)
# ans.append(node.val)
# inorder(node.right)class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
vector<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) {
while (cur) {
stk.push_back(cur);
cur = cur->left;
}
cur = stk.back();
stk.pop_back();
ans.push_back(cur->val);
cur = cur->right;
}
return ans;
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)（显式栈或递归栈，最坏链状树）
常见坑
弹出栈顶后忘记 cur = cur.right：会死循环或漏掉右子树，中序变成「只输出左链」。
在压栈循环里就 append 节点值：那是前序（根在左走之前），中序必须在弹出时记录。
空树 root == nullptr：外层 while (cur || !stk.empty()) 应直接不进入，返回空数组，不要访问空指针。
必测边界 Case
root = [] → []
root = [1] → [1]
root = [1,2,null,3] → [3,2,1]（栈深度为树高）
root = [1,null,2,3] → [1,3,2]