二叉树遍历详解：前序、中序、后序和层序

遍历顺序为什么重要

树没有唯一的自然顺序，所以算法会选择适合任务的那一种。对二叉搜索树做中序遍历，会按从小到大的顺序得到所有键。前序先访问父节点再访问孩子，复制一棵树或把树写出来以便重建时需要它。后序先访问孩子再访问父节点，删除一棵树、计算文件夹大小或求值表达式树时需要它。层序最先找到最浅的节点，也能逐行打印一棵树。

同一棵树上的四种顺序

我们使用这棵树：根节点 1 有孩子 2 和 3；节点 2 有孩子 4 和 5；节点 3 有右孩子 6。

        1
       / \
      2   3
     / \   \
    4   5   6

记住前三种的简单办法：名字说明了节点放在哪里。前（pre）表示在两棵子树之前，中（in）表示在它们之间，后（post）表示在它们之后。左子树总是先于右子树被访问。

递归实现

递归版本直接对应定义。每个函数在不同的一行访问节点。

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

用栈实现迭代的前序和中序

递归使用调用栈。为了避免在很深的树上触及递归限制，可以自己管理栈。对于前序，弹出一个节点并访问它，然后先压入右孩子再压入左孩子，这样左孩子会先被处理。

对于中序，尽可能向左走，沿途把节点压入栈。当不能再往左走时，弹出一个节点并访问它，然后转向它的右孩子。

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

迭代的后序和层序

迭代的后序最棘手。一种清晰的做法是使用标志位：每个节点压入两次，第二次标记为“孩子处理完后再访问”。层序用队列而不是栈；一次处理队列中的一整层，还能顺便得到每个节点的深度。

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

后序的另一个常见技巧：先运行修改过的前序（根、右、左），再把结果反转。

时间与空间复杂度

这里 n 是节点数，h 是高度，w 是最大宽度。对平衡树来说，h 约为 log2(n)，w 可达约 n/2；对链状的树来说，h 是 n，w 是 1。

常见错误

• 在迭代的前序中先压左孩子再压右孩子。栈是 LIFO，所以想先处理的孩子必须最后压入。
• 忘记空树：每个函数对 root is None 都应返回空结果。
• 在层序中用 list 加 pop(0) 当队列。每次弹出是 O(n)；请使用 collections.deque。
• 对很深的树依赖递归。Python 到达递归限制（默认约 1000）时会抛出 RecursionError。
• 指望单一的遍历结果就能确定一棵树。仅有前序是有歧义的；前序加中序（值互不相同时）才足以重建。

何时使用哪种遍历

前序、中序和后序都是深度优先搜索的形式；层序则是应用在树上的广度优先搜索。同样的思路可以推广到一般的图，只是还需要一个已访问节点的集合。