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（栈溢出），此时需考虑迭代写法。

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，性能更佳且语义更清晰。
    • 注意空指针的处理和循环终止条件。

12. 二叉树-BFS

0 - 算法, 0.0 - 算法模版

正文

二叉树的广度优先搜索（BFS）通常用于层序遍历（Level-order Traversal）。它的特点是按照从上到下、从左到右的顺序逐层访问节点。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.ArrayDeque

fun bfs(root: TreeNode?) {
    if (root == null) return
    
    // 使用队列保存每一层的节点
    val queue = ArrayDeque<TreeNode>()
    queue.offer(root)
    
    while (queue.isNotEmpty()) {
        // 当前层的节点数量
        val levelSize = queue.size
        
        // 遍历当前层的所有节点
        for (i in 0 until levelSize) {
            val node = queue.poll()
            visit(node)

            // 将下一层的节点入队
            node.left?.let { queue.offer(it) }
            node.right?.let { queue.offer(it) }
        }
    }
}

使用说明

  1. 核心技巧：

    • 队列（Queue）：利用队列的“先进先出”特性。
    • **levelSize**：通过记录当前队列的大小，可以精确控制每一层节点的遍历，适用于需要区分层级的题目。

  2. 常见变形：

    • 层平均值：在遍历每一层时计算平均值。
    • 右视图：每一层遍历的最后一个节点即为右视图可见节点。
    • Z 字形遍历：利用双端队列或在输出结果时进行翻转。
    • 寻找最小深度：第一个到达叶子节点时的层数即为最小深度。

  3. 性能分析：

    • 时间复杂度：$O(N)$。
    • 空间复杂度：$O(W)$，其中 $W$ 是二叉树的最大宽度。在完全二叉树中，最后一层节点数约为 $N/2$。

  4. 注意点：

    • 在 Kotlin 中，ArrayDeque 是实现队列的最佳选择。
    • 入队前务必检查子节点是否为空。

13. 图-DFS (递归)

0 - 算法, 0.0 - 算法模版

正文

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
class Graph {
    private val adjList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjList.getOrPut(u) { mutableListOf() }.add(v)
    }

    fun dfs(vertex: Int) {
        val visited = mutableSetOf<Int>()
        dfsHelper(vertex, visited)
    }

    private fun dfsHelper(vertex: Int, visited: MutableSet<Int>) {
        visited.add(vertex)
        println(vertex) // 在这里可以对当前节点进行相关操作

        val neighbors = adjList[vertex]
        if (neighbors != null) {
            for (neighbor in neighbors) {
                if (!visited.contains(neighbor)) {
                    dfsHelper(neighbor, visited)
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    graph.addEdge(3, 4)

    // 从节点 0 开始进行深度优先搜索
    graph.dfs(0)
}

14. 图-DFS (迭代)

0 - 算法, 0.0 - 算法模版

正文

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
class Graph {
    private val adjacencyList: MutableMap<Int, MutableList<Int>> = mutableMapOf()

    fun addEdge(u: Int, v: Int) {
        adjacencyList.computeIfAbsent(u) { mutableListOf() }.add(v)
    }

    fun dfs(start: Int) {
        val visited = mutableSetOf<Int>()
        val stack = mutableListOf<Int>()

        stack.add(start)
        while (stack.isNotEmpty()) {
            val vertex = stack.removeAt(stack.size - 1)
            if (!visited.contains(vertex)) {
                visited.add(vertex)
                println("Visited vertex: $vertex")

                adjacencyList[vertex]?.reversed()?.forEach { neighbor ->
                    if (!visited.contains(neighbor)) {
                        stack.add(neighbor)
                    }
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()

    // 添加图的边
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 5)
    graph.addEdge(2, 6)

    // 从顶点0开始进行DFS
    graph.dfs(0)
}

15. 图-BFS

0 - 算法, 0.0 - 算法模版

正文

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
import java.util.*

class Graph {
    private val adjacencyList: MutableMap<Int, MutableList<Int>> = HashMap()

    fun addEdge(src: Int, dest: Int) {
        adjacencyList.computeIfAbsent(src) { mutableListOf() }.add(dest)
        adjacencyList.computeIfAbsent(dest) { mutableListOf() }
    }

    fun bfs(startVertex: Int) {
        val visited = BooleanArray(adjacencyList.size)
        val queue: Queue<Int> = LinkedList()

        visited[startVertex] = true
        queue.offer(startVertex)

        while (!queue.isEmpty()) {
            val currentVertex = queue.poll()
            print("$currentVertex ")

            val neighbors = adjacencyList[currentVertex]
            if (neighbors != null) {
                for (neighbor in neighbors) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true
                        queue.offer(neighbor)
                    }
                }
            }
        }
    }
}

fun main() {
    val graph = Graph()
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)

    println("BFS traversal starting from vertex 2:")
    graph.bfs(2)
}

16. 找到堆的前 k 个元素

0 - 算法, 0.0 - 算法模版

正文

“找到第 K 大的元素”或“找到前 K 个高频元素”是堆（Heap/PriorityQueue）最经典的应用场景。利用堆的特性，可以将原本需要全排序的 $O(N \log N)$ 复杂度优化到 $O(N \log K)$。

算法模板 (找到第 K 大的元素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.PriorityQueue

fun findKthLargest(nums: IntArray, k: Int): Int {
    // 技巧：求第 K 大用最小堆；求第 K 小用最大堆
    // 创建最小堆 (PriorityQueue 默认即为最小堆)
    val minHeap = PriorityQueue<Int>()

    // 将数组中的元素依次加入最小堆
    for (num in nums) {
        minHeap.offer(num)

        // 如果最小堆的大小超过 k，移除堆顶元素
        // 这样堆中始终保留的是目前遍历过的最大的 k 个元素
        if (minHeap.size > k) {
            minHeap.poll()
        }
    }

    // 最小堆的堆顶就是这 k 个最大值中最小的一个，即第 k 大的元素
    return minHeap.peek()
}

使用说明

  1. 核心逻辑：

    • 求前 K 大：维护一个大小为 $K$ 的最小堆。当堆满时，新元素若大于堆顶，则弹出堆顶并插入新元素。最终堆中留下的就是最大的 $K$ 个数，堆顶是第 $K$ 大。
    • 求前 K 小：维护一个大小为 $K$ 的最大堆（PriorityQueue(Collections.reverseOrder())）。堆顶是这 $K$ 个最小值中最大的一个，即第 $K$ 小。

  2. 核心优势：

    • 空间效率：不需要加载全部数据，只需维持 $K$ 个元素的堆。
    • 时间效率：$O(N \log K)$。当 $K \ll N$ 时，性能接近 $O(N)$。

  3. 常见变形：

    • 前 K 个高频元素：配合哈希表记录频率，堆中存储 Map.Entry 并根据频率排序。
    • 合并 K 个有序链表：利用最小堆维护 $K$ 个链表的当前头节点。
    • 数据流中的第 K 大：保持堆的大小为 $K$，持续 offer 和 poll。

  4. 注意点：

    • 在 Kotlin/Java 中，PriorityQueue 默认是最小堆（队首是最小值）。
    • 如果需要最大堆，需传入比较器：PriorityQueue<Int> { a, b -> b - a }。
    • 对于海量数据处理，堆是内存占用最友好的方案。

17. 二分查找

0 - 算法, 0.0 - 算法模版

正文

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的核心思想是通过不断将搜索区间减半，来极大地提高搜索效率。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        // 使用该方式计算 mid 防止 (left + right) 导致整型溢出
        val mid = left + (right - left) / 2

        if (nums[mid] == target) {
            // 找到目标，返回索引
            return mid
        } else if (nums[mid] < target) {
            // 目标在右半部分，收缩左边界
            left = mid + 1
        } else {
            // 目标在左半部分，收缩右边界
            right = mid - 1
        }
    }

    // 未找到目标元素
    return -1
}

使用说明

  1. 先决条件：

    • 数据必须是有序的（通常是升序）。
    • 必须支持随机访问（即数组或列表，链表不适用）。

  2. 核心技巧：

    • **计算 mid**：建议使用 val mid = left + (right - left) / 2，而不是 (left + right) / 2。这是为了避免当 left 和 right 都很大时相加导致 Int 溢出。
    • 循环条件：while (left <= right) 意味着搜索区间是闭区间 [left, right]。

  3. 复杂度分析：

    • 时间复杂度：$O(\log N)$。
    • 空间复杂度：$O(1)$。

  4. 注意点：

    • 注意边界处理：left = mid + 1 和 right = mid - 1，确保每次循环都能缩小搜索区间，防止死循环。
    • 如果数组中存在重复元素，该模板返回的是其中任意一个目标的索引。若需查找“最左侧”或“最右侧”插入点，请参考后续专门的二分模板。

18. 二分查找-重复元素，最左边的插入点

0 - 算法, 0.0 - 算法模版

正文

当数组中存在重复元素时，标准的二分查找只能随机返回其中一个目标的索引。如果我们需要找到第一个出现的目标元素（最左侧边界），或者目标不存在时其应插入的位置，需要使用以下变体。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun searchLeftBound(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2
        
        if (nums[mid] >= target) {
            // 如果中间值大于等于目标，说明左边界在左侧（包含当前 mid）
            // 我们继续向左收缩以寻找“第一个”目标
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    // 此时 left 就是最左侧的插入点
    // 如果要判断 target 是否存在：
    // if (left < nums.size && nums[left] == target) return left else return -1
    return left
}

使用说明

  1. 核心逻辑：

    • 关键在于 nums[mid] >= target 时执行 right = mid - 1。即使找到了目标，我们也并不立即返回，而是继续收缩右边界，试图在左侧找到更早出现的目标。
    • 循环结束后，left 变量的值即为大于等于 target 的第一个元素的索引。

  2. 适用场景：

    • 查找有序数组中第一个等于 target 的元素。
    • 查找第一个大于等于 target 的元素（Lower Bound）。
    • 统计重复元素的个数（通过左右边界相减）。

  3. 注意点：

    • 返回值 left 的范围是 [0, nums.size]。如果 target 比数组所有元素都大，left 将等于 nums.size。
    • 检查是否存在时，务必先判断 left < nums.size。

19. 二分查找-重复元素，最右边的插入点

0 - 算法, 0.0 - 算法模版

正文

当数组中存在重复元素时，如果我们需要寻找目标元素出现的最后一次索引位置（最右侧边界），或者目标不存在时其应插入的位置，需要使用以下变体。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fun searchRightBound(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2
        
        if (nums[mid] <= target) {
            // 如果中间值小于等于目标，说明右边界可能在右侧
            // 我们继续向右移动以寻找“最后一个”目标
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    // 此时 right 就是最右侧的插入点（即最后一个小于等于 target 的元素位置）
    // 或者说 left 是第一个大于 target 的元素位置
    return right
}

使用说明

  1. 核心逻辑：

    • 关键在于 nums[mid] <= target 时执行 left = mid + 1。即使找到了目标，我们也并不立即返回，而是继续收缩左边界，试图在右侧寻找最后一次出现的目标。
    • 循环结束后，right 指向的是最后一个等于 target 的元素索引。

  2. 适用场景：

    • 查找有序数组中最后一个等于 target 的元素。
    • 查找最后一个小于等于 target 的元素（Upper Bound 变体）。
    • 统计重复元素的范围（配合左边界模板）。

  3. 注意点：

    • 返回值 right 的范围是 [-1, nums.size - 1]。如果 target 比数组所有元素都小，right 将为 -1。
    • 检查是否存在时，务必先判断 right >= 0。
    • left 的最终位置是第一个大于 target 的元素位置。