二叉树在面试实战中，花样非常多。本节只是个开头，在后面几个专题、包括最后的大厂真题实战环节中，我们都不会停止对二叉树相关考点的学习和探讨。

在本节，有以下三个命题方向需要大家重点掌握：

• 迭代法实现二叉树的先、中、后序遍历
• 二叉树层序遍历的衍生问题
• 翻转二叉树

这三个方向对应的考题都比较经典。与此同时，解决这些问题涉及到的思路和编码细节，也会成为各位日后解决更加复杂的问题的基石。因此，虽然本节篇幅略长，但还是希望各位能够倾注耐心，给自己充分的时间去理解和消化这些知识。

“遍历三兄弟”的迭代实现

⚡ 30 秒速记

• 递归隐含使用调用栈；改迭代就是显式保存“稍后还要处理”的节点。
• 前序 根-左-右：弹出根后先压右、再压左。
• 中序：一路压左，栈空前弹出访问，再转向右子树。
• 后序最容易错，可用 根-右-左 结果反转，或栈中保存 visited 状态。

三种遍历的迭代实现，本质上都是用栈安排结点的处理顺序，只是根结点被访问的时机不同。 前序遍历要得到“根、左、右”，弹出当前结点后应先压入右孩子，再压入左孩子，因为栈是后进先出。中序遍历则要沿左孩子一路入栈，走到最左侧后再逐个弹出并转向右子树。空树直接返回空数组，结果中保存的是结点值，而不是结点对象。

回答参考：“三种遍历的区别只是访问根节点的时机。迭代实现要把递归栈里的返回点显式化，我会先说栈内节点代表什么，再写循环。”

function inorder(root) {
  const result = []
  const stack = []
  let current = root
  while (current || stack.length) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    result.push(current.val)
    current = current.right
  }
  return result
}

💬 面试官追问

• 评论区有人说中序遍历也能像前序一样“根节点出栈就立刻输出”，你拿页面上的 左 -> 根 -> 右 规则怎么构造反例？

  只要根节点存在左孩子，根一出栈就输出便会早于左子树，直接违反 左 -> 根 -> 右。中序迭代必须先沿 left 一路压栈，直到没有左节点，再弹出并访问根；根的输出时机不能照搬前序框架。

• 你在白板上写页面里的 inorder(root)，面试官追问 stack 中的节点究竟代表什么，你会怎样结合两个 while 解释？

  stack 保存的是沿左链经过、但尚未输出的祖先节点，相当于显式记录递归返回点。内层 while 持续压入左侧路径，外层循环弹出最近祖先并访问，再把 current 转向其右子树；两部分共同完成回溯。

• 组件树从普通深度变成一条只有右孩子的链，current || stack.length 这个循环条件还成立吗，流程会怎样变化？

  条件仍然成立，每轮内层循环只压入当前节点一次，随后立即弹出、输出并转向右孩子。即使 stack 暂时为空，只要 current 指向下一个节点，外层循环就必须继续；若只判断 stack.length，遍历会提前终止。

• 线上埋点发现中序结果漏掉右子树，而左侧节点顺序正常；你会优先检查页面示例中的哪两行状态迁移？

  先检查弹栈输出之后是否执行了 current = current.right，以及外层条件是否保留 current || stack.length。前者缺失会永远不进入右子树，后者若只看栈可能在转向右孩子时提前结束；可用根节点带单个右孩子的最小用例复现。

• 代码评审中，一方主张分别维护三套遍历代码，另一方要求统一成 { node, visited } 模板；就当前中序页面你如何取舍？

  页面代码直接把中序的“沿左链下探—弹栈访问—转向右侧”表达出来，状态含义清晰，适合单独维护和讲解。标记模板能统一形式，却引入额外栈帧状态；若团队更看重可读性，不必为了统一而隐藏中序的游标逻辑。