题目描述
按中序(左根右)返回二叉树所有节点的值。
思路解析
递归版只有「递归左、访问根、递归右」三行，看着简单。可它把真正的执行顺序都交给了系统调用栈——你看不见「现在轮到谁、回头还要访问谁」，一旦面试官让你不用递归写，立刻卡壳。
转折：递归的本质就是「一路往左压栈，到底了弹出来访问，再转向右子树」。我们用一个显式栈亲手模拟这个过程——压栈代替「往左递归」，弹栈访问代替「该访问自己了」，转右代替「递归右子树」。栈替你记住了回头要访问谁。
一路压左 · cur=4 入栈：cur 从根 4 出发。规矩：只要 cur 不为空，就把 cur 压栈、再往左走。先把 4 压栈，cur 移到它的左孩子 2。
一路压左 · cur=2 入栈：cur=2 不为空，继续压栈、往左：2 压入栈，cur 移到它的左孩子 1。栈里现在记着「4、2 都还没轮到访问」。
一路压左 · cur=1 入栈：cur=1 还不为空，再压一次：1 入栈，cur 移到它的左孩子。可是 1 没有左孩子，cur 变成空——一路向左到底了。
到底 · 弹栈访问 1：cur 为空，说明左边走到头了：弹出栈顶 1 并访问它(结果加 1)。这一步就是中序的「根」时机——左子树(空)走完，才轮到自己。1 没有右孩子，cur 仍为空。
cur 仍空 · 弹栈访问 2：cur 还是空，继续弹栈访问：弹出 2，访问它(结果加 2)。对 2 来说，左孩子 1 已经访问过，现在轮到根。访问完转向它的右孩子 3，cur=3。
转右 · cur=3 入栈：cur=3 不为空，又回到「压栈、往左」：3 压栈，往左走。3 没有左孩子，cur 立刻变空——这是个无左孩子的负例：压完马上就要弹出来访问。
到底 · 弹栈访问 3：cur 空，弹出 3 访问(结果加 3)。3 也没有右孩子，cur 仍为空。左子树 (1,2,3) 至此全部访问完毕，栈里只剩根 4。
cur 空 · 弹栈访问根 4：cur 空，弹出栈顶 4 访问(结果加 4)。4 的左子树全走完了，现在才轮到根——访问完转向它的右孩子 6，cur=6。栈暂时空了，但 cur 不空，还没结束。
转右 · cur=6 入栈：cur=6 不为空，照旧「压栈、往左」：6 压栈，往左走。6 是叶子没有左孩子，cur 变空。
完成 · 弹栈访问 6 · 升序：cur 空，弹出 6 访问(结果加 6)。现在栈空且 cur 也空，循环结束。最终结果 [1,2,3,4,6]，正好升序——这是 BST 中序遍历的招牌性质。
所有「不用递归改写遍历」的题，本质都是自己拿一个栈，模拟系统帮你做的事：下钻就压栈、该处理某节点就弹出来、处理完转向下一个方向。中序把「访问」放在弹栈之后、转右之前，换个位置就是前序/后序。
参考代码（Python）
1def inorderTraversal(self, root):
2 res, stack = [], []
3 cur = root
4 while cur or stack: # 还有没走完的左路 或 栈里有待访问
5 while cur: # ① 一路压左到底
6 stack.append(cur)
7 cur = cur.left
8 cur = stack.pop() # ② 弹出 = 该访问它了
9 res.append(cur.val) # 访问根(中序时机)
10 cur = cur.right # ③ 转向右子树
11 return res复杂度分析
- 时间复杂度：O(n) —— 每个节点恰好入栈一次、出栈一次，共 2n 次操作
- 空间复杂度：O(h) —— 栈里最多同时存一条「根到当前」的路径，长度就是树高 h；最坏退化成链状时 O(n)
套路模板
记住骨架：外层 while cur 或 stack、内层 while cur 一路压左、弹栈访问、转右。这套「压左 → 弹访问 → 转右」的迭代模板能直接背去面试，是不用递归遍历二叉树的通用写法。
1res, stack, cur = [], [], root
2while cur or stack: # 循环条件：两者有一个非空就继续
3 while cur: # 一路压左到底
4 stack.append(cur)
5 cur = cur.left
6 cur = stack.pop() # 弹出并访问
7 res.append(cur.val) # 中序：在这里收集
8 cur = cur.right # 转向右子树易错点
- 错误写法：把「访问根」写在压栈时(变成了前序顺序) → 正确写法：必须在弹栈之后、转右之前才 res.append(cur.val)（中序是左根右：先把左边一路压到底，弹出来时左子树已走完，这时访问才是「根」的正确时机；写在压栈时就成了根左右(前序)）
- 错误写法：外层循环只写 while stack → 正确写法：while cur or stack（访问完一个节点转到 cur.right 后栈可能暂时为空(如访问完根 4 时)，但右子树还没走，只判 stack 会提前退出、漏掉右子树）
- 错误写法：压栈后忘了 cur = cur.left，或漏了转 cur = cur.right → 正确写法：内层往左、访问后往右，两个方向都不能少（不往左会死循环压同一个节点；不转右则永远走不进右子树）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。