中序、前序、后序 DFS
使用显式栈递归或迭代实现三种 DFS 遍历，并说明每种顺序适用的场景。
中序、前序、后序 DFS 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
DFS 的三种遍历顺序
二叉树的 DFS 根据根节点相对于其子节点何时被处理，分为三种顺序。前序：根节点 → 左子树 → 右子树。中序：左子树 → 根节点 → 右子树。后序：左子树 → 右子树 → 根节点。这些名称说明了根节点在序列中的位置。理解这三种顺序非常重要，因为不同问题需要使用不同的顺序。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')递归前序遍历
在前序遍历中，当前节点在其子树之前被处理。这对应于从上到下阅读树的自然方式，可用于复制树、序列化以及计算前缀表达式。递归实现非常简短，但会构建深度为 O(h) 的调用栈，其中 h 是树的高度。
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]递归中序遍历
中序遍历会先访问左子树，再访问根节点，最后访问右子树。对于二叉搜索树，中序遍历总会产生一个有序序列——验证 BST、第 k 小元素以及 BST 转有序数组等问题都会利用这一性质。对于 BST 问题，这是最重要、最需要掌握的遍历方式。
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!递归后序遍历
后序遍历会在当前节点之前处理两个子节点。这种自底向上的顺序适用于父节点的计算依赖子节点结果的情况，例如计算子树大小、删除树或计算表达式树。大多数将信息向上传递的树问题，都会使用隐式的后序逻辑。
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]使用栈进行迭代前序遍历
为避免递归深度限制，可以使用显式栈迭代实现 DFS。对于前序遍历：先压入根节点，然后在每次迭代中弹出一个节点并记录它，接着先压入右子节点，再压入左子节点（先压入右子节点，这样左子节点会先被处理）。这种方式模拟了调用栈的 LIFO 行为，是处理深层树的首选方法，因为 Python 默认的递归限制为 1000，超过该深度就会失败。
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]使用栈进行迭代中序遍历
迭代中序遍历稍微复杂一些。使用一个栈和一个指针 curr：尽可能向左移动，并将沿途的每个节点压入栈中。当无法继续向左时，弹出节点并记录它，然后向右移动。这种一直向左压入直到为空，弹出并处理，然后向右移动的模式，是一种常用的迭代技巧，也会出现在 BST 迭代器问题中。
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]使用两个栈进行迭代后序遍历
迭代后序遍历有一个巧妙的技巧：运行一种修改后的前序遍历（根节点 → 右子树 → 左子树），然后反向收集结果。压入根节点，弹出节点并将其添加到结果开头，再压入左子节点和右子节点。反转操作会将根节点-右子树-左子树转换为左子树-右子树-根节点，这正是后序遍历。另一种方法是使用 prev 指针，通过一个栈跟踪最后访问的节点。
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]如何选择遍历方式
选择正确的遍历方式是面试中的关键信号。需要在处理子节点之前处理父节点时，使用前序遍历（序列化树、复制结构）。对于 BST，使用中序遍历来利用有序性。计算依赖两个子节点的值时，使用后序遍历（高度、直径、子树和）。对于最短路径和按层分组的问题，优先使用 BFS。
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6莫里斯遍历：O(1) 空间的中序遍历
莫里斯遍历通过临时修改树，在中序遍历中实现 O(1) 的空间复杂度。对于每个有左子树的节点，找到中序前驱（左子树中最右侧的节点），并将其右指针连接回当前节点。访问完成后，恢复该连接。当面试官问“能否使用 O(1) 的额外空间完成？”时，顶级面试通常会考查这种高级技巧。
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]根据遍历结果重建树
给定前序和中序数组，可以重建原始树。前序数组的第一个元素总是根节点。在中序数组中找到该根节点——它左侧的所有元素属于左子树，右侧的所有元素属于右子树。对这些子数组递归执行相同操作。使用哈希表进行索引查找时，时间复杂度为 O(n)。
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20遍历的时间与空间复杂度总结
三种 DFS 遍历的时间复杂度都是O(n)，因为每个节点恰好被访问一次。空间复杂度为O(h)，其中 h 是树的高度——平衡树为 O(log n)，退化树为 O(n)（空间来自调用栈或显式栈）。迭代实现可以避免 Python 的递归限制，但渐进空间复杂度相同。莫里斯遍历通过复用树的右指针，独特地实现了 O(1) 的空间复杂度。
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')快速检查
测试您对本课中数据结构 & 算法——编程面试准备相关概念的理解。
课程回顾
本课介绍了：三种 DFS 遍历顺序（前序、中序、后序）以及每种顺序的适用时机，使用显式栈的递归和迭代实现，以及莫里斯 O(1) 空间技巧。接下来我们将探索如何计算二叉树的直径、高度和平衡性。
常见问题解答
「中序、前序、后序 DFS」课时是免费的吗？
是的 — 「中序、前序、后序 DFS」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「中序、前序、后序 DFS」这节课中我会学到什么？
使用显式栈递归或迭代实现三种 DFS 遍历，并说明每种顺序适用的场景。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「中序、前序、后序 DFS」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- TreeNode 类与层序 BFS
- 中序、前序、后序 DFS
- 直径、高度与平衡树
- 路径和与最近公共祖先