本篇题目#

二叉树基础回顾#

中序遍历（左 → 根 → 右）#

BST 的中序遍历天然输出升序结果，这是后两道题的核心性质。

1
    3
2
   / \
3
  1   4
4
   \
5
    2
6

7
中序遍历：1 → 2 → 3 → 4  （天然升序）

中序遍历没有显式的”遍历列表”，顺序完全靠递归调用的位置保证：

1
def dfs(root):
2
    dfs(root.left)   # ① 先递归到最左
3
    # 处理当前节点   # ② 自己
4
    dfs(root.right)  # ③ 再去右边

dfs(root.left) 不返回，当前节点就永远轮不到——这是一个逐层解包的过程，必须把最内层的拆完才能处理外层的。

LeetCode 102 · 二叉树的层序遍历#

#102二叉树的层序遍历

Medium

思路#

用队列做 BFS，每次处理完整的一层再进入下一层。关键在于用 range(len(deque)) 固定当前层的节点数，这样内层 for 循环结束后正好处理完一整层。

代码#

1
class Solution:
2
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
3
        if not root: return []
4
        res, deque = [], collections.deque([root])
5
        while deque:
6
            tmp = []
7
            for _ in range(len(deque)):   # 固定当前层节点数
8
                node = deque.popleft()
9
                tmp.append(node.val)
10
                if node.left: deque.append(node.left)
11
                if node.right: deque.append(node.right)
12
            res.append(tmp)
13
        return res

执行过程#

1
初始：deque = [3]
2

3
第1层：range(1) → 处理 3，deque 变成 [1, 4]，tmp = [3]
4
第2层：range(2) → 处理 1、4，deque 变成 [2]，tmp = [1, 4]
5
第3层：range(1) → 处理 2，deque 变成 []，tmp = [2]
6

7
结果：[[3], [1, 4], [2]]

LeetCode 103 · 二叉树的锯齿形层序遍历#

#103二叉树的锯齿形层序遍历

Medium

思路#

在 102 的基础上，奇偶层输出方向不同。核心技巧：不改变 BFS 的遍历顺序，只改变每个值插入 tmp 的位置——偶数层追加到尾部，奇数层插入到头部，天然反转。

奇偶层判断#

1
if len(res) % 2 == 0:
2
    tmp.append(node.val)      # 第0、2、4...层：左→右
3
else:
4
    tmp.appendleft(node.val)  # 第1、3、5...层：右→左（头部插入=反转）

判断发生在 res.append(tmp) 之前，所以 len(res) 恰好等于当前层的索引。

为什么 appendleft 能反转？#

BFS 永远从左到右遍历子节点，对于需要”右→左”输出的层，把每个值插到 tmp 头部，后来的反而排前面，自动完成反转：

1
遍历顺序：  A → B → C
2
appendleft：C  B  A   ← 天然反转，O(1) 头插代替 reverse

代码#

1
class Solution:
2
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
3
        if not root: return []
4
        res, deque = [], collections.deque([root])
5
        while deque:
6
            tmp = collections.deque()
7
            for _ in range(len(deque)):
8
                node = deque.popleft()
9
                if len(res) % 2 == 0: tmp.append(node.val)
10
                else: tmp.appendleft(node.val)
11
                if node.left: deque.append(node.left)
12
                if node.right: deque.append(node.right)
13
            res.append(list(tmp))
14
        return res

LeetCode 230 · 二叉搜索树中第K小的元素#

#230二叉搜索树中第K小的元素

Medium

思路#

BST 中序遍历 = 升序输出，第 K 次访问的节点就是第 K 小的元素。不需要把所有值存起来再排序，用一个倒计数器，减到 0 的那一刻就是答案。

代码#

1
class Solution:
2
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
3
        def dfs(root):
4
            if not root: return
5
            dfs(root.left)
6
            if k == 0: return      # 已找到答案，后续节点全部跳过
7
            nonlocal k, res
8
            k -= 1
9
            if k == 0: res = root.val
10
            dfs(root.right)
11

12
        res = 0
13
        dfs(root)
14
        return res

关键细节#

① nonlocal k, res 是什么？

内层函数可以读外层变量，但不能直接修改。nonlocal 显式声明”我要修改外层的 k 和 res”，否则 k -= 1 会报 UnboundLocalError。

另一种写法是用 self.k、self.res 挂在实例上，效果相同，只是绕开了闭包限制：

1
# 用 self 的版本
2
self.k = k
3
def dfs(root):
4
    self.k -= 1   # self.k 不受闭包限制，可以直接改

② if k == 0: return 为什么写在 k -= 1 前面？

这行拦住的是”上一轮已经找到答案”的情况，防止当前节点多执行一次 k -= 1 导致 k 变成 -1。顺序至关重要：

1
dfs(root.left)         # 左子树可能已经找到答案，k 已经是 0 了
2
if k == 0: return      # ← 先检查，如果是 0 就不处理当前节点了
3
k -= 1                 # 消费当前节点
4
if k == 0: res = root.val
5
dfs(root.right)

③ root 不是指根节点

递归过程中 root 这个名字有点误导——只有第一次调用时它才是真正的根节点，之后每层递归里的 root 都是”当前正在访问的节点”，叫 node 或 curr 更准确，但习惯上大家复用这个名字。

④ if k == 0: res = root.val 为什么在 k -= 1 之后？

因为 k -= 1 就在上一行，减完之后等于 0，说明已经访问了恰好 k 个节点，当前节点就是第 k 小的：

1
self.k = 1
2
self.k -= 1  →  self.k = 0    ← 说明已访问了 k 个节点
3
self.k == 0  →  res = root.val ← 当前节点就是答案

执行过程（k=3）#

1
    3
2
   / \
3
  1   4
4
   \
5
    2
6

7
dfs(3)
8
  └─ dfs(1)
9
       └─ dfs(None) → 返回
10
       k: 3→2，访问 1
11
       └─ dfs(2)
12
            └─ dfs(None) → 返回
13
            k: 2→1，访问 2
14
            └─ dfs(None) → 返回
15
  k: 1→0，访问 3  ← res = 3，找到答案！
16
  └─ dfs(4)
17
       if k==0: return  ← 直接跳过，不再处理

中序遍历是一个逐层解包的过程：dfs(root.left) 不返回，当前节点就永远轮不到，保证了访问顺序天然是升序。

总结#

核心思路：BST 中序遍历 = 升序，nonlocal 计数器倒计到 0
复杂度：时间 O(H + k)，H 为树高，空间 O(H)

LeetCode 215 · 数组中的第K个最大元素#

#215数组中的第K个最大元素

Medium

思路一：排序（简洁但非最优）#

1
class Solution:
2
    def findKthLargest(self, nums: List[int], k: int) -> int:
3
        return sorted(nums)[len(nums) - k]

sorted 从小到大，倒数第 k 个就是第 k 大：

1
nums = [3,2,1,5,6,4]，k = 2
2
sorted → [1, 2, 3, 4, 5, 6]
3
len - k = 6 - 2 = 4
4
[4]   → 5  ← 第2大

时间 O(n log n)，面试中一般需要更优解。

思路二：最小堆（推荐）#

维护一个大小为 k 的最小堆，堆里始终保留当前最大的 k 个数，堆顶就是第 k 大的元素。

1
class Solution:
2
    def findKthLargest(self, nums: List[int], k: int) -> int:
3
        heap = []
4
        for num in nums:
5
            heapq.heappush(heap, num)
6
            if len(heap) > k:
7
                heapq.heappop(heap)   # 弹出最小值，保留最大的 k 个
8
        return heap[0]                # 堆顶 = 第 k 大

heapq 三个核心函数#

函数	作用	时间复杂度
`heapify(h)`	把普通列表原地变成最小堆	O(n)
`heappush(h, val)`	插入一个元素	O(log k)
`heappop(h)`	取出并返回最小值	O(log k)

Python 的堆是最小堆，h[0] 可以直接查看堆顶（最小值）而不弹出。

执行过程（k=2）#

1
nums = [3,2,1,5,6,4]
2

3
push 3 → [3]
4
push 2 → [2, 3]          len==k，不弹出
5
push 1 → [1, 2, 3] → 弹出1 → [2, 3]
6
push 5 → [2, 3, 5] → 弹出2 → [3, 5]
7
push 6 → [3, 5, 6] → 弹出3 → [5, 6]
8
push 4 → [4, 5, 6] → 弹出4 → [5, 6]
9

10
heap[0] = 5  ← 第2大的元素 ✓

堆始终只保留 k 个元素，堆顶（最小的那个）就是”最大的 k 个里最小的”，即第 k 大。

两种方法对比#

	排序	最小堆
时间复杂度	O(n log n)	O(n log k)
空间复杂度	O(n)	O(k)
适用场景	快速实现	面试首选，k 远小于 n 时更优

总结#

核心思路：大小为 k 的最小堆，堆顶即答案
复杂度：时间 O(n log k)，空间 O(k)

四题横向对比#

题目	核心数据结构	关键技巧
102 层序遍历	队列（BFS）	`range(len(deque))` 固定每层节点数
103 锯齿形层序	双端队列	`appendleft` 代替 reverse，O(1) 头插
230 第K小元素	递归调用栈	BST 中序 = 升序，nonlocal 倒计数
215 第K大元素	最小堆	维护大小为 k 的堆，堆顶即答案

IMPORTANT
中序遍历的本质 没有显式的”遍历列表”，顺序靠递归结构保证：dfs(root.left) 写在前面，意味着必须把最左边的全部处理完才能回头处理自己。这是一个逐层解包的过程，调用栈天然维护了”左 → 根 → 右”的顺序。