二叉树遍历：前序/中序/后序遍历（递归与迭代）、层序遍历、二叉树的最大深度
二叉树遍历，可以说是面试中的「送分题」，也是「送命题」。
说它送分，是因为套路固定。说它送命，是因为很多人只背了递归，一让写迭代就卡壳。我当年面试某大厂时，面试官让我手写非递归的中序遍历，我愣是想了五分钟才磕磕绊绊写出来。嗯，从那以后，我就把迭代遍历刻进了肌肉记忆。
一、二叉树的遍历方式总览
先搞清楚一件事：遍历顺序是由「根节点」的位置决定的。
| 遍历方式 | 访问顺序 | 典型应用场景 |
|---|---|---|
| 前序遍历 | 根 → 左 → 右 | 序列化二叉树、复制树结构 |
| 中序遍历 | 左 → 根 → 右 | 二叉搜索树的有序输出 |
| 后序遍历 | 左 → 右 → 根 | 删除树、计算子树大小 |
| 层序遍历 | 逐层从左到右 | 求树宽、最短路径 |
说白了，你只要记住「根在哪，就叫什么序」。根在前就是前序，根在中就是中序，根在后就是后序。
二、递归遍历——最直观，但别只会背
递归写法，三行代码搞定。但我建议你理解它的调用栈，而不是死记硬背。
// 前序遍历
func preorder(_ root: TreeNode?) {
guard let root = root else { return }
print(root.val) // 根
preorder(root.left) // 左
preorder(root.right) // 右
}
// 中序遍历
func inorder(_ root: TreeNode?) {
guard let root = root else { return }
inorder(root.left)
print(root.val)
inorder(root.right)
}
// 后序遍历
func postorder(_ root: TreeNode?) {
guard let root = root else { return }
postorder(root.left)
postorder(root.right)
print(root.val)
}
我的小技巧： 写递归时，先想好「终止条件」和「单层逻辑」。终止条件就是节点为空，单层逻辑就是按顺序访问根、左、右。其他层递归会自动帮你搞定。
三、迭代遍历——面试真正的考点
递归虽然简单，但面试官往往要求你写迭代版本。为什么？因为递归有栈溢出风险，而且能考察你对栈这种数据结构的理解。
3.1 前序遍历（迭代）
前序遍历的迭代写法是最简单的。你想想看，根先访问，然后左子树，再右子树。用栈的话，应该先压右子节点，再压左子节点。这样出栈时左子节点先被处理。
func preorderIteration(_ root: TreeNode?) -> [Int] {
var result = [Int]()
var stack = [TreeNode]()
var node = root
while node != nil || !stack.isEmpty {
while node != nil {
result.append(node!.val) // 访问根
stack.append(node!)
node = node!.left // 向左走
}
node = stack.removeLast()
node = node?.right // 转向右子树
}
return result
}3.2 中序遍历（迭代）
中序遍历的迭代写法，我个人觉得是最容易出错的。核心思想是：一路向左压栈，直到没有左子节点，然后出栈访问，再转向右子树。
func inorderIteration(_ root: TreeNode?) -> [Int] {
var result = [Int]()
var stack = [TreeNode]()
var node = root
while node != nil || !stack.isEmpty {
while node != nil {
stack.append(node!)
node = node!.left
}
node = stack.removeLast()
result.append(node!.val) // 访问根
node = node?.right
}
return result
}
我曾经踩过的坑： 写中序遍历时，容易在访问完根节点后忘记把 node 指向右子节点。结果就是死循环，一直在左子树里打转。调试了半小时才发现，嗯，这种低级错误犯一次就够了。
3.3 后序遍历（迭代）
后序遍历的迭代写法稍微麻烦一点。因为根节点最后访问，需要记录上一个访问的节点，防止重复入栈。
func postorderIteration(_ root: TreeNode?) -> [Int] {
var result = [Int]()
var stack = [TreeNode]()
var node = root
var lastVisited: TreeNode? = nil
while node != nil || !stack.isEmpty {
while node != nil {
stack.append(node!)
node = node!.left
}
let top = stack.last!
if top.right == nil || top.right === lastVisited {
result.append(top.val)
lastVisited = stack.removeLast()
} else {
node = top.right
}
}
return result
}这里的关键是：当右子树为空，或者右子树已经被访问过了，才访问当前节点。否则先去处理右子树。
四、层序遍历——BFS 的典型应用
层序遍历用队列实现，这个套路在「树的广度优先搜索」里随处可见。
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var result = [[Int]]()
var queue = [root]
while !queue.isEmpty {
var level = [Int]()
let count = queue.count
for _ in 0..<count {
let node = queue.removeFirst()
level.append(node.val)
if let left = node.left { queue.append(left) }
if let right = node.right { queue.append(right) }
}
result.append(level)
}
return result
}
注意： 每次循环开始前，先记录当前队列的长度。这个长度就是当前层的节点数。如果不这样做，队列里会混入下一层的节点，导致分层错误。我在项目中用层序遍历做「树形菜单的扁平化展示」时，就靠这个技巧搞定的。
五、二叉树的最大深度
求最大深度，说白了就是求根节点到最远叶子节点的距离。递归写法极其优雅：
func maxDepth(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
return max(maxDepth(root.left), maxDepth(root.right)) + 1
}一行核心逻辑：左子树深度和右子树深度的最大值，加上当前节点这一层。
迭代写法呢？用层序遍历，每遍历一层深度加一：
func maxDepthIteration(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var queue = [root]
var depth = 0
while !queue.isEmpty {
let count = queue.count
for _ in 0..<count {
let node = queue.removeFirst()
if let left = node.left { queue.append(left) }
if let right = node.right { queue.append(right) }
}
depth += 1
}
return depth
}六、面试实战建议
- 先写递归，再优化迭代： 面试时如果时间紧张，先给出递归版本，表明你理解核心逻辑。然后主动说「我还可以用迭代实现，避免栈溢出」。
- 画图辅助： 写迭代遍历时，我习惯在纸上画一个简单的二叉树，手动模拟栈的变化。这样不容易出错。
- 边界条件： 空树、单节点树、只有左子树的树、只有右子树的树。这些情况都要在脑子里过一遍。
总结一下： 二叉树遍历是算法面试的「基本功」。递归考思路，迭代考细节。层序遍历和最大深度是 BFS 的入门题。把这些吃透了，后面遇到「之字形遍历」「右视图」「最近公共祖先」等问题，你就能举一反三了。
好了，这一章的内容就到这里。下一章我们会聊二叉搜索树的增删改查，那又是另一番天地了。