二叉树遍历的多种进化

3.1 二叉树遍历的多种进化

本节摘要：二叉树是递归思想的正式主场。本节从递归遍历的极简形态出发，讲清前中后序只是"处理当前节点时机"的排列组合，再进化到迭代遍历与层序遍历，最后以莫里斯遍历收尾——它把空间开销压到常数级，是遍历进化链的终点。

树形结构呼唤递归

第二章学过的递归在链表与数组上多少有点大材小用，到了树上才真正如鱼得水：树本身就是递归定义的——一棵二叉树，要么是空，要么由根加左右两棵子树构成。这个定义直接翻译成遍历代码。理解本节的主线只需抓住个观察：前序、中序、后序的差别，仅仅是"处理当前节点"这个动作放在递归左右子树之前、之间还是之后。时机不同，输出的用途就不同：前序适合复制树与序列化，中序对二叉搜索树恰好输出有序序列，后序适合自底向上汇总（如求子树高度、删节点）。

先立好结构与一道热身题（求最大深度），感受递归在树上的简洁：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_depth(root):
    if root is None:                 # 基准：空树深度为零
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# 构造      1
#          / \
#         2   3
#        / \
#       4   5
n4, n5 = TreeNode(4), TreeNode(5)
n2 = TreeNode(2, n4, n5)
n3 = TreeNode(3)
root = TreeNode(1, n2, n3)
print(max_depth(root))    # 输出 3
​

一、递归三序：三行代码的排列组合

def preorder(node, out):        # 根左右：用于复制、序列化
    if node is None:
        return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node, out):         # 左根右：二叉搜索树输出有序
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

def postorder(node, out):       # 左右根：自底向上汇总
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)

res = []
preorder(root, res);  print(res)    # 输出 [1, 2, 4, 5, 3]
res = []
inorder(root, res);   print(res)    # 输出 [4, 2, 5, 1, 3]
res = []
postorder(root, res); print(res)    # 输出 [4, 5, 2, 3, 1]
​

递归遍历时间 O(n)（每节点访问一次），空间 O(h)，h 为树高——调用栈深度。最坏情况（链状退化树）h 等于 n，空间 O(n)；平衡树 h 约 log n。中序遍历对二叉搜索树的有序性是最常考的性质：验证一棵树是否为搜索树，中序一遍顺手检查相邻元素是否递增即可，前提是小心"只比较父子"的错误写法——必须保证整体有序，而非局部有序。

二、迭代化与层序：把递归显式化

递归的弱点是调用栈不可控。迭代版用显式栈接管：前序最简单，出栈访问、先压右孩子再压左孩子（栈后进先出，要先访问左边就得后压）。中序迭代稍绕：一路向左压栈，到头弹栈访问，再转向右子树。后序最 tricky，用"前序改造（根右左）再整体倒序"的技巧最不易错。

def preorder_iter(root):
    out, stack = [], []
    if root:
        stack.append(root)
    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 node or stack:
        while node:                    # 一路向左压到底
            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]
print(inorder_iter(root))    # 输出 [4, 2, 5, 1, 3]
​

层序遍历换了维度：不按深度优先，按层推进，武器从栈换成队列。逐层输出的实现要点是用当层节点数控制内层循环：

from collections import deque

def level_order(root):
    if root is None:
        return []
    out, 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)
        out.append(level)
    return out

print(level_order(root))    # 输出 [[1], [2, 3], [4, 5]]
​

三、莫里斯遍历：常数的极限压榨

遍历进化链的终点是莫里斯遍历：利用树中大量空闲的空指针，在中序前驱的最右节点上临时建立回指线索，访问完顺着线索回到祖先再拆除线索。全程不使用栈也不改树的结构（结束后还原），空间 O(1)。代价是逻辑更绕、且遍历过程中树被临时改动——多线程环境不可用。面试中通常不要求现场默写，但"知道遍历空间能压到常数"本身是区分度所在，能讲清线索机制即可加分。

本节要点回顾

• 三序同源：差别只在处理当前节点的时机，前序复制、中序有序、后序汇总；
• 空间复杂度是树高：链状退化树递归深度达 n，这是迭代化要解决的问题；
• 中序迭代模式：一路向左压栈、弹栈访问、转向右子树，值得默写；
• 层序用队列、按当层个数控制循环即可逐层输出；
• 莫里斯遍历：借空指针建线索，空间压到 O(1)，代价是临时改树。

下一节登场的是堆：当问题反复索要"当前最值"，全排序就是浪费——堆把这个操作的代价压到对数级。