11. 二叉树-DFS (迭代)

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

当树的深度较大时，递归可能会导致栈溢出。此时，我们可以使用显式栈来模拟递归过程，实现二叉树的深度优先搜索（DFS）。

1. 先序遍历 (根 -> 左 -> 右)

最简单的迭代写法，利用栈“后进先出”的特性，先压右孩子再压左孩子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fun preorderTraversal(root: TreeNode?) {
    if (root == null) return
    val stack = java.util.ArrayDeque<TreeNode>()
    stack.push(root)

    while (stack.isNotEmpty()) {
        val current = stack.pop()
        visit(current)
        
        // 注意：先压右再压左，这样出栈顺序就是先左再右
        current.right?.let { stack.push(it) }
        current.left?.let { stack.push(it) }
    }
}

2. 中序遍历 (左 -> 根 -> 右)

中序遍历的逻辑是：一直往左走到底，然后回溯处理根节点，最后处理右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fun inorderTraversal(root: TreeNode?) {
    val stack = java.util.ArrayDeque<TreeNode>()
    var cur = root

    while (cur != null || stack.isNotEmpty()) {
        // 1. 一直向左走，将路径上的节点入栈
        while (cur != null) {
            stack.push(cur)
            cur = cur.left
        }

        // 2. 弹出栈顶元素并访问
        val node = stack.pop()
        visit(node)

        // 3. 转向右子树
        cur = node.right
    }
}

3. 后序遍历 (左 -> 右 -> 根)

后序遍历是迭代写法中最难的一种，关键在于判断右子树是否已经访问过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fun postorderTraversal(root: TreeNode?) {
    val stack = java.util.ArrayDeque<TreeNode>()
    var cur = root
    var lastVisited: TreeNode? = null
    
    while (cur != null || stack.isNotEmpty()) {
        while (cur != null) {
            stack.push(cur)
            cur = cur.left
        }
        
        val peekNode = stack.peek()
        // 如果右子树为空，或者右子树刚刚被访问过，则访问当前节点
        if (peekNode.right == null || peekNode.right == lastVisited) {
            visit(peekNode)
            lastVisited = stack.pop()
        } else {
            // 否则，转向右子树
            cur = peekNode.right
        }
    }
}

使用说明

  1. 核心技巧：

    • 先序：根节点先处理，利用栈保存待处理的左右子节点。
    • 中序：利用栈实现“回溯”功能，记住来时的路。
    • 后序：需要一个额外的 lastVisited 指针来标记右子树的状态，防止陷入死循环。

  2. 性能优势：

    • 避免了递归调用的开销。
    • 空间复杂度为 $O(H)$，在极端不平衡的树下比递归更安全。

  3. 注意点：

    • 在 Kotlin 中，建议使用 ArrayDeque 代替 Stack 或 LinkedList，性能更佳且语义更清晰。
    • 注意空指针的处理和循环终止条件。
0 - 算法, 0.0 - 算法模版