核心要点
前序=根左右、中序=左根右、后序=左右根，三者递归写法只是「访问根」的位置不同
迭代写法用栈模拟递归；层序遍历用队列做 BFS，按层取出节点
复杂度：每个节点访问一次，时间 O(n)，递归栈/显式栈空间 O(h)，h 为树高
标准回答
二叉树遍历分深度优先（前、中、后序）和广度优先（层序）两类。前中后序的区别仅在于处理根节点相对于左右子树的先后：前序先根，中序根在中间，后序最后处理根；递归实现非常直观，迭代实现则用栈显式模拟递归调用。层序遍历用队列实现 BFS，逐层把节点出队并把其孩子入队即可。下面给出中序的递归与迭代写法，以及层序遍历：
python
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_recursive(root):
# 中序递归：左 -> 根 -> 右
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val) # 访问根的时机决定了是哪种序
dfs(node.right)
dfs(root)
return res
def inorder_iterative(root):
# 中序迭代：用栈一路压左孩子，弹出时访问，再转向右孩子
res, stack, cur = [], [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
def level_order(root):
# 层序遍历：队列 BFS，按层分组
if not root:
return []
res, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # 当前层节点数
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
if __name__ == '__main__':
# 1
# / \
# 2 3
# /
# 4
root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(inorder_recursive(root)) # [4, 2, 1, 3]
print(inorder_iterative(root)) # [4, 2, 1, 3]
print(level_order(root)) # [[1], [2, 3], [4]]常见误区
⚠️ 常见踩坑
迭代中序里 cur 转向右孩子后不要重新从 root 开始；层序遍历忘记用 len(q) 锁定当前层节点数，会把下一层混入当前层。
追问
追问 1：三种 DFS 遍历的时间和空间复杂度？
时间均为 O(n)，每个节点访问常数次。空间为递归栈或显式栈深度 O(h)：平衡树 O(log n)，退化成链表时 O(n)。
追问 2：如何不用递归也不用额外栈实现中序遍历？
用 Morris 遍历：利用叶子的空右指针建立指向后继的临时线索，遍历后再断开，空间降到 O(1)，时间仍为 O(n)。代价是会临时修改树结构。
延伸学习
与本题相关的知识库文章、术语、工具与行业资讯。