二叉树的中序遍历
Binary Tree Inorder Traversal
按中序遍历（左 → 根 → 右）返回二叉树的所有节点值。
在力扣中练习题目描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题思路
主解法
栈 · 迭代中序
一路向左压栈，弹出即访问，再转向右子树
中序的顺序是“左子树全部访问完，才轮到根，最后是右子树”。递归写法很直接，但面试常要求用栈模拟。
从 cur 出发，只要 cur 不为空就压栈并向左走到底。此时栈顶是最左节点，弹出并访问它；它的左子树必然已经处理完，于是把 cur 指向它的右子树，继续同样的过程。
分步图解
cur 指向根，栈和 res 为空；先沿左孩子一直走到底。
当前节点与已访问节点
栈 · 栈顶是下一个要访问的根
从栈顶进入与离开
访问一个节点后，右子树可能为空，也可能是一整条新的左链；后者会再次压栈。栈里保存的正是“还没访问根”的祖先，所以右子树处理完后能回到上一层。
分步图解
弹出并访问 2；它的左子树已经处理完，接下来转向右子树。
- res.size
- 2
当前节点与已访问节点
栈 · 栈顶是下一个要访问的根
2↑ 出栈
- 6← top
自拟树左侧比右侧深，节点 1、2 的右孩子又各有分支；这能看出“访问根”和“转向右子树”是两个不同的时刻，不能合并成一次左-右扫描。
时间 O(n)空间 O(h)
易错点
- 只压栈不向左走：栈里会同时出现左右孩子，顺序错乱。
- 弹出后直接继续弹出：忘记把 cur 指向右子树，右子树永远不被访问。
- 循环条件只写 !st.empty()：根为空但 cur 初始不为空时会漏掉整棵树。
对照解法
递归 · 中序
左子树 → 根 → 右子树，三行写完
代码最短，但递归深度等于树高，最坏 O(n) 调用栈；迭代版把栈显式化。
递归版本把“处理左子树”和“处理右子树”交给调用栈：先递归左孩子，再把当前值加入结果，最后递归右孩子。
它和迭代版访问节点的顺序完全一致，只是栈由运行时维护。树退化成链时递归深度为 n，可能栈溢出；迭代版同样需要 O(h) 的显式栈，但更容易控制。
面试里两种写法都应该会：递归负责表达思路，迭代负责证明你理解栈的作用。
- 1空节点直接返回。
- 2递归左子树。
- 3把当前节点值加入结果。
- 4递归右子树。
时间 O(n)空间 O(h)
易错点
- 先访问根再递归左子树：变成前序。
- 忘记处理空节点：递归无法终止。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
root = [6,2,9,1,4,8,11,null,null,3,5]cur 指向根，栈和 res 为空；先沿左孩子一直走到底。
当前节点与已访问节点
栈 · 栈顶是下一个要访问的根
从栈顶进入与离开
查看 C++ 代码
延伸阅读
- 前序、中序、后序的区别只在“访问根”放在两次递归的哪个位置；栈的压入顺序也随之变化。
- 中序迭代的模板可以直接复用到验证 BST、第 k 小元素等题。