3月22日刷题笔记

本篇题目#

一、理解递归的核心思想#

不要试图在脑子里追踪每一层调用，只想当前节点该做什么，子树的事交给递归。

IMPORTANT
递归三步法

base case → 空节点返回什么？

当前层逻辑 → 这个节点做什么？

组合结果 → 用左右子树的结果拼出当前结果

万能模板：

1
def solve(root):
2
    if not root:          # 1. base case
3
        return ...
4

5
    do_something(root)    # 2. 当前节点逻辑
6

7
    left  = solve(root.left)   # 3. 交给递归
8
    right = solve(root.right)
9

10
    return combine(root, left, right)

二、102. 二叉树的层序遍历（BFS）#

#102二叉树的层序遍历

Medium

核心：用 deque，右边进左边出，每轮用 len(queue) 快照当前层节点数

1
from collections import deque
2

3
def levelOrder(root):
4
    if not root:
5
        return []
6

7
    result = []
8
    queue = deque([root])       # 初始化：根节点入队
9

10
    while queue:
11
        level_size = len(queue) # 快照当前层节点数
12
        level = []
13

14
        for _ in range(level_size):   # _ 表示不需要循环变量
15
            node = queue.popleft()    # O(1) 头部取出
16
            level.append(node.val)
17
            if node.left:  queue.append(node.left)
18
            if node.right: queue.append(node.right)
19

20
        result.append(level)
21

22
    return result

TIP
为什么用 deque 不用 list？ list.pop(0) 是 O(n)，因为要把后面所有元素往前移；deque.popleft() 是 O(1)，专门为队列设计。

三、617. 合并二叉树（递归典型题）#

#617合并二叉树

Easy

思路：只想当前节点，两树都有就值相加，有一个为空就返回另一个

1
def mergeTrees(root1, root2):
2
    if not root1: return root2   # 一棵为空，返回另一棵
3
    if not root2: return root1
4

5
    node = TreeNode(root1.val + root2.val)  # 当前节点相加
6
    node.left  = mergeTrees(root1.left,  root2.left)   # 交给递归
7
    node.right = mergeTrees(root1.right, root2.right)
8
    return node

四、常见语法速查#

1
# deque 初始化
2
queue = deque([root])     # 等价于 deque() + append(root)
3
queue = deque([1, 2, 3])  # 用列表初始化多个元素
4

5
# _ 占位符：只想循环 N 次，不需要循环变量
6
for _ in range(n):
7
    ...
8

9
# 判空写法（三种等价，推荐 is None 最精确）
10
if not root:        # 最简洁，常用
11
if root is None:    # 最精确，推荐
12
if root == None:    # 不推荐（可被 __eq__ 覆盖）