二叉树的中序遍历

问题拆解

中序遍历的规则是：先访问左子树，再访问根，最后访问右子树。递归写法几乎不用动脑，但题目进阶要求用迭代完成，这才是值得琢磨的地方。

难点在于：递归之所以简单，是因为函数调用栈帮我们记住了「处理完左子树后，还得回到当前节点、再去处理右子树」。改成迭代，就得自己用一个栈把这条「回头路」显式管理起来。

迭代版遍历的本质，是手动复刻递归调用栈干的活。

递归写法

def inorderTraversal(root):
    result = []

    def visit(node):
        if not node:
            return
        visit(node.left)
        result.append(node.val)
        visit(node.right)

    visit(root)
    return result

三行顺序就是中序定义本身，改一改顺序就能得到前序或后序。

显式栈迭代

用一个指针 cur 一路向左把节点压栈，走到底后弹出访问，再转向它的右子树：

def inorderTraversal(root):
    result, stack = [], []
    cur = root

    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        result.append(cur.val)
        cur = cur.right

    return result

内层循环负责「尽量往左」，弹栈时机就对应递归里「左子树处理完了」的那一刻，访问完当前值后把 cur 指向右孩子，循环会自动对右子树重复同样的过程。

复杂度

指标	复杂度	原因
时间	O(n)	每个节点入栈、出栈各一次
空间	O(h)	栈里最多存一条从根到当前节点的路径

可以迁移的模式

• 任何递归都能用显式栈改写成迭代，关键是想清楚「栈里存的是待返回的现场」；
• 「一路向某个方向走到底，再回退」的结构，天然对应压栈—弹栈；
• 遍历顺序的差异只在访问根节点的时机，框架可以复用。

当递归深度可能失控、或面试要求手写栈时，这套「模拟调用栈」的思路就派上用场了。