练习题

基础题

130. 被围绕的区域(Medium)

搜索一圈边上的区域，记录所有与边界相连的 O ，所有内部的 O 都填充为 X

样例

X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

代码

def dfs(i, j, visited, board):
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:
        return 

    if board[i][j] != "O":
        return 
    
    visited[i][j] = 1
    dfs(i + 1, j, visited, board)
    dfs(i - 1, j, visited, board)
    dfs(i, j + 1, visited, board)
    dfs(i, j - 1, visited, board)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board: return 
        n, m = len(board), len(board[0])
        visited = [[0] * m for _ in range(n)]
        # 搜索周围一圈
        for i in range(m):
            dfs(0, i, visited, board)
            dfs(n - 1, i, visited, board)
        
        for i in range(1, n - 1):
            dfs(i, 0, visited, board)
            dfs(i, m - 1, visited, board)
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O' and not visited[i][j]:
                    board[i][j] = 'X'

257. 二叉树的所有路径(Easy)

使用回溯法

def dfs(root, ans, tmp):
    if not root: return 
    tmp.append(str(root.val))
    if not root.left and not root.right:
        ans.append('->'.join(tmp))
    dfs(root.left, ans, tmp)
    dfs(root.right, ans, tmp)
    tmp.pop()
        
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        ans = []
        dfs(root, ans, [])
        return ans 

进阶

310. 最小高度树(Medium)

本题思路难，编程也有不少坑。参考了：最容易理解的bfs，分析简单，注释详细

思路上：使用BFS搜索，不断删除叶子节点，经过有限次的删除，最后一定剩下 1 或 2 个的节点。

编程上：

• 如何实现? 使用临接矩阵实现
• 如何删除叶子节点? 只调整节点的 degree，不用删除 link 临接矩阵的关系
• 什么时候判断找到结果？ 节点只剩1-2个，实现上，直接每次保证最后的queue。当循环结束的时候，最后一个 queue 就是结果。

from collections import defaultdict, deque 
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if not edges: 
            return [0]

        degree = [0] * n
        link = defaultdict(list)
        for edge in edges:
            degree[edge[0]] += 1 # 节点的度
            degree[edge[1]] += 1
            link[edge[0]].append(edge[1])
            link[edge[1]].append(edge[0])
        queue = deque()  
        for i in range(n):
            if degree[i] == 1:
                queue.append(i)
            
        while queue:
            res = list(queue)  # 最后一层是我们的答案!!!
            for _ in range(len(queue)):
                node = queue.popleft()
                for next_node in link[node]:
                    degree[next_node] -= 1 
                    if degree[next_node] == 1: # 去除 node 后变成叶子节点(度为1)
                        queue.append(next_node)
        return res