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

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

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

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

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

⚡ 30 秒速记

• 递归背后是调用栈；改迭代就是自己用栈记住「之后还要回来处理」的节点
• 先序（根左右）：弹出就记录，先压右再压左
• 中序（左根右）：一路向左压栈到底 → 弹出记录 → 转向右子树
• 后序（左右根）：按「根右左」收集后整体反转，或者用 lastVisited 标记
• 中序外层条件是 cur || stack.length，两个都不能少

三种遍历改成迭代，本质都是用栈模拟递归，区别只在根节点什么时候被记录。 先序最简单：弹出一个节点就记录，然后先压右孩子再压左孩子，因为栈是后进先出，左边要先处理就得后压。中序不一样，根不能一弹出就记，要先沿着 left 一路压栈走到最左边，弹出来记录，再把游标转到它的右子树重复这个过程。后序常用的技巧是先按「根右左」得到序列，最后整个反转成「左右根」。

function inorder(root) {
  const res = [], stack = []
  let cur = root
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left } // 一路向左
    cur = stack.pop()
    res.push(cur.val)                               // 左边处理完，记录根
    cur = cur.right                                 // 转向右子树
  }
  return res
}

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

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
}

💬 面试官追问

• 中序能不能像先序一样，节点一出栈就记录、再压左右孩子？

  不行。只要根有左孩子，根一出栈就记录，它就排在左子树前面了，违反「左根右」。中序必须先一路向左压栈，左边处理完才轮到根。

• 中序迭代里，stack 里的节点到底代表什么？

  代表「左子树还没处理完、自己还没输出」的祖先节点，相当于递归里那些在等左子树返回的调用帧。弹出一个就等于左递归结束了，接着处理根、进入右子树。

• 树是一条只有右孩子的链，外层只写 while (stack.length) 会怎样？

  弹出根、转向右孩子时栈刚好是空的，循环就提前结束了，只输出第一个节点。必须写 cur || stack.length，cur 不为空说明还有右子树要处理。

• 中序结果漏掉了所有右子树，左边顺序是对的，先看哪一行？

  看弹栈记录后有没有 cur = cur.right。漏了这行，游标永远不会进入右子树。拿「根只带一个右孩子」的三行用例就能复现。