04 树 / 图 / BFS & DFS

数据结构基础

🔖 #200 · Number of Islands ★

难度: Medium | 标签: Graph, BFS/DFS | 链接: https://leetcode.com/problems/number-of-islands/

题目描述

给定二维网格，计算岛屿数量。

解题思路

DFS 每遇到 '1'，计数器 +1，并递归将连通的 '1' 标记为 '0'。

答案代码

def numIslands(grid):
    def dfs(i, j):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '0'
        for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(i+di, j+dj)
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

扩展总结

  • 也可用 Union Find，处理动态并查返回当前岛数更高效
  • 变体：#695 Max Area of Island，#305 Number of Islands II

🔖 #207 · Course Schedule ★

难度: Medium | 标签: Graph, Topological Sort | 链接: https://leetcode.com/problems/course-schedule/

题目描述

判断是否可以完成所有课程安排（检测有向图中是否有环）。

解题思路

拓扑排序 (Kahn's BFS)：
  1. 计算入度数组
  1. 将所有入度为0的节点入队
  1. 逐层弹出，更新邻居节点入度
  1. 如果最终处理的节点数 = n，无环

答案代码

from collections import deque
def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    q = deque(i for i in range(numCourses) if indegree[i] == 0)
    count = 0
    while q:
        node = q.popleft()
        count += 1
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                q.append(nei)
    return count == numCourses

扩展总结

  • #210 Course Schedule II：返回实际拓扑排序序列
  • DFS 法：用 GRAY/BLACK 连色检测环

🔖 #236 · Lowest Common Ancestor

难度: Medium | 标签: Tree, DFS | 链接: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

找二叉树中两个节点的最近公共祖先。

解题思路

递归：如果当前节点是 p 或 q，返回自身。否则递归左右子树，如果两边均非空，当前节点即为 LCA。

答案代码

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if left and right else left or right

扩展总结

  • #235 BST 版本：可利用 BST 单调性更简单
  • #1644 LCA of Binary Tree II： p 或 q 可能不在树中

🔖 #124 · Binary Tree Maximum Path Sum

难度: Hard | 标签: Tree, DFS | 链接: https://leetcode.com/problems/binary-tree-maximum-path-sum/

题目描述

找二叉树中路径和最大的路径。

解题思路

后序递归：每个节点返回且只返回单侧最大贡献。在计算 res 时考虑经过当前节点的左+右+自身路径。

答案代码

def maxPathSum(root):
    res = [root.val]
    def dfs(node):
        if not node:
            return 0
        l = max(dfs(node.left), 0)
        r = max(dfs(node.right), 0)
        res[0] = max(res[0], node.val + l + r)
        return node.val + max(l, r)
    dfs(root)
    return res[0]

扩展总结

  • 关键：递归返回吃 "单侧最大贡献"，全局最大在 res 中更新
  • 相关：#543 Diameter of Binary Tree—类似后序递归模型