10. 二叉树-DFS (递归)

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

正文

二叉树的深度优先搜索（DFS）递归写法是最直观的，其本质是利用了系统的函数调用栈。

算法模板

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
class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun dfs(root: TreeNode?) {
    // 递归终止条件
    if (root == null) return
    
    // 1. 先序遍历 (Pre-order): 根 -> 左 -> 右
    // visit(root)
    
    dfs(root.left)  
    
    // 2. 中序遍历 (In-order): 左 -> 根 -> 右
    // visit(root)
    
    dfs(root.right)  
    
    // 3. 后序遍历 (Post-order): 左 -> 右 -> 根
    // visit(root)
}

fun visit(node: TreeNode) {
    println(node.value)
}

使用说明

  1. 三种遍历顺序：

    • 先序：常用于复制二叉树、序列化二叉树。
    • 中序：二叉搜索树（BST）的中序遍历是有序序列。
    • 后序：常用于计算二叉树的高度、删除二叉树。

  2. 核心优势：

    • 逻辑极其简单，符合人类直觉。
    • 代码量极少，易于实现。

  3. 性能分析：

    • 时间复杂度：$O(N)$，每个节点访问一次。
    • 空间复杂度：$O(H)$，其中 $H$ 是树的高度。最坏情况下（倾斜树）为 $O(N)$。

  4. 注意点：

    • 递归必须有明确的终止条件（通常是 root == null）。
    • 如果树的深度极大，可能会导致 StackOverflowError（栈溢出），此时需考虑迭代写法。
0 - 算法, 0.0 - 算法模版