算法 - 二叉树前中后序遍历（迭代写法）

Posted on

1. 题目

给定二叉树的根节点 root，分别返回它的前序（根左右）、中序（左根右）、后序（左右根）遍历，要求使用迭代（显式栈）而非递归。

示例:

1
2
3
4
5
6
7
8
9
        1
         \
          2
         /
        3

前序: [1, 2, 3]
中序: [1, 3, 2]
后序: [3, 2, 1]

节点定义：

1
2
3
4
5
6
7
8
9
10
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}

2. 解题思路

递归的本质是系统调用栈，迭代就是自己用一个显式栈模拟。

  • 前序：栈弹出即「访问」。为了让左子树先处理，压栈时先压右、再压左。

  • 中序：一路 push 左孩子到底（此时栈顶是最左节点），弹出访问，再转向它的右子树。核心是「访问时机 = 左边走到头之后」。

  • 后序：最难。技巧——后序 = 左、右、根，若按「根、右、左」访问再整体反转，就得到「左、右、根」。于是复用前序框架（先压左、再压右），最后 reverse()。

  • 时间复杂度：均为 O(n)。

  • 空间复杂度：O(h)，h 为树高（栈大小），最坏 O(n)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 前序：根 -> 左 -> 右
function preorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    if (!root) return res;
    const stack: TreeNode[] = [root];

    while (stack.length) {
        const node = stack.pop()!;
        res.push(node.val);                 // 访问根
        if (node.right) stack.push(node.right); // 先压右
        if (node.left) stack.push(node.left);   // 再压左，保证左先弹出
    }
    return res;
}

// 中序：左 -> 根 -> 右
function inorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    const stack: TreeNode[] = [];
    let curr = root;

    while (curr || stack.length) {
        while (curr) {         // 一路向左压栈
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop()!;   // 弹出最左节点
        res.push(curr.val);    // 访问根
        curr = curr.right;     // 转向右子树
    }
    return res;
}

// 后序：左 -> 右 -> 根（用「根右左 + 反转」）
function postorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    if (!root) return res;
    const stack: TreeNode[] = [root];

    while (stack.length) {
        const node = stack.pop()!;
        res.push(node.val);                // 根
        if (node.left) stack.push(node.left);  // 先压左
        if (node.right) stack.push(node.right); // 再压右，得到「根右左」
    }
    return res.reverse();                  // 反转为「左右根」
}

console.log(preorder(new TreeNode(1, null, new TreeNode(2, new TreeNode(3)))));
// [1,2,3]
console.log(postorder(new TreeNode(1, null, new TreeNode(2, new TreeNode(3)))));
// [3,2,1]

4. 面试延伸

  • 统一模板：可给栈里放 {node, visited} 标记，用「访问」和「展开孩子」两态统一三种序，写法一致但空间略大。
  • Morris 遍历：利用叶子节点的空闲右指针（线索化）做到 O(1) 额外空间，是迭代之上的高区分度加分项。
  • 层序遍历（BFS） 用队列，与本题用栈（DFS）形成对照，别混。
  • 追问常考：为什么后序用「根右左再反转」而不是直接模拟？——直接模拟需要记录「右子树是否已访问」，逻辑更绕，反转法最简洁。

难度：中等 | LeetCode 144/94/145 题 | 栈模拟递归