本篇题目#

常见二叉树类型与性质#

Complete Binary Tree 完全二叉树#

每层从左到右填满，最后一层可以不满但必须靠左
编号规律（从 1 开始）：左孩子 = 父 × 2，右孩子 = 父 × 2 + 1
堆（heap）就是用数组实现的完全二叉树，利用的正是这套下标规律

IMPORTANT
完全二叉树编号规律是 LeetCode 662 的核心
不管实际树长什么样，按完全二叉树规则给节点编号：左孩子 = 父 × 2，右孩子 = 父 × 2 + 1。同一层宽度 = 最右编号 − 最左编号 + 1，中间的空节点自动被计入。

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

7
最后一层靠左排列，是完全二叉树 ✓

Perfect Binary Tree 满二叉树（中文叫法）#

每一层全部填满，节点总数恰好是 2ⁿ - 1

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

7
每层全满，节点数 = 2³ - 1 = 7 ✓

TIP
中英文差异
英文 Full Binary Tree ≠ 中文满二叉树。Full 在英文里指每个节点要么 0 个孩子要么 2 个孩子；中文满二叉树对应的英文是 Perfect Binary Tree。看英文资料时留意。

Binary Search Tree (BST) 二叉搜索树#

左子树所有节点 < 根，右子树所有节点 > 根，每棵子树也满足此性质
查找、插入、删除平均 O(log n)，最坏退化成链表 O(n)

1
      5
2
    /   \
3
   3     8
4
  / \   / \
5
 1   4 7   9
6

7
中序遍历：1 3 4 5 7 8 9  ← 严格升序 ✓

TIP
刷题常用结论
BST 的中序遍历结果是升序序列，遇到”验证 BST”或”第 K 小元素”类题目优先想中序遍历。

Balanced Binary Tree 平衡二叉树#

任意节点的左右子树高度差不超过 1
常见实现：AVL 树、红黑树

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

9
左边：高度差最大为 1，是平衡树 ✓
10
右边：右侧一直延伸，退化成链表 ✗

TIP
刷题写法
判断是否平衡用后序遍历，返回子树高度，一旦高度差 > 1 就返回 -1 向上传递”已不平衡”的信号，避免重复计算。

LeetCode 662 · 二叉树最大宽度#

#662二叉树最大宽度

Medium

思路#

普通 BFS 无法计算宽度，因为中间的空节点不在队列里，数不出来。

关键想法：借用完全二叉树的编号规则给每个节点编号。不管实际树长什么样，都按完全二叉树的规则假设编号存在。这样同一层最右节点编号 - 最左节点编号 + 1 就是这层宽度，中间跳过的空位自动被算进去。

代码#

1
class Solution:
2
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
3
        if not root: return 0
4

5
        # 记录全局最大宽度
6
        ans = 0
7
        # 队列存 (编号, 节点)，根节点编号为 1
8
        # 编号规则和完全二叉树一样：左孩子=父*2，右孩子=父*2+1
9
        queue = deque([(1, root)])
10

11
        while queue:
12
            # 每轮处理一整层
13
            # 初始化为正无穷，保证第一个 code 一定能更新 min_seen
14
            min_seen = inf
15
            # 初始化为 0，保证第一个 code 一定能更新 max_seen
16
            max_seen = 0
17

18
            # len(queue) 是当前层的节点数，循环只处理这一层
19
            for i in range(len(queue)):
20
                code, node = queue.popleft()
21

22
                # 把下一层的子节点连同编号一起入队
23
                if node.left: queue.append((code * 2, node.left))
24
                if node.right: queue.append((code * 2 + 1, node.right))
25

26
                # 更新本层出现过的最小编号（最左节点）
27
                min_seen = min(code, min_seen)
28
                # 更新本层出现过的最大编号（最右节点）
29
                max_seen = max(code, max_seen)
30

31
            # 本层宽度 = 最右编号 - 最左编号 + 1
32
            # 中间跳过的空节点因为编号连续，自动被算进去了
33
            ans = max(ans, max_seen - min_seen + 1)
34

35
        return ans

总结#

核心技巧：把额外信息（编号）打包进元组和节点一起入队，是 BFS 题的常见写法
复杂度：时间 O(n)，空间 O(n)（队列最多存一层节点）

TIP
编号溢出问题
树很深时编号指数级增长，可以在每层开始时把所有编号减去本层 min_seen 归一化，只保留相对差值。Python 整数不会溢出，但 Java / C++ 需要特别注意。

TIP
inf 和 0 的初始化技巧
找最小值初始化为正无穷 inf，找最大值初始化为 0（或负无穷），保证第一个真实值一定能更新它，不需要额外判断”是否是第一个元素”。

LeetCode 111 · 二叉树的最小深度#

#111二叉树的最小深度

Easy

思路#

BFS 按层遍历，第一次遇到叶子节点时，当前层数就是最小深度，直接返回。

TIP
注意坑
最小深度不是单纯找最短路径，必须到达叶子节点（左右都为空）才算终点。如果用递归直接取 min(左深度, 右深度)，当某侧子树为空时会返回 0，导致结果偏小。BFS 天然规避了这个问题，遇到叶子才返回，不会被空子树干扰。
1
    1
2
   /
3
  2
4

5
递归错误写法：min(dfs(左)=1, dfs(右)=0) = 0，答案错误
6
BFS 正确：第 2 层遇到叶子节点 2，返回深度 2 ✓

代码#

1
from collections import deque
2

3
class Solution:
4
    def minDepth(self, root: Optional[TreeNode]) -> int:
5
        if not root:
6
            return 0
7

8
        queue = deque([root])  # 队列只存节点，不需要带额外信息
9
        depth = 0              # 记录当前层数
10

11
        while queue:
12
            depth += 1  # 进入新的一层，深度 +1
13

14
            for _ in range(len(queue)):  # 处理当前层所有节点
15
                node = queue.popleft()
16

17
                # 把下一层的子节点入队
18
                if node.left:
19
                    queue.append(node.left)
20
                if node.right:
21
                    queue.append(node.right)
22

23
                # 遇到叶子节点，当前 depth 就是最小深度，直接返回
24
                if not node.left and not node.right:
25
                    return depth
26

27
        return depth

总结#

核心技巧：BFS 天然按层遍历，第一个叶子节点一定是最浅的，直接返回无需比较
复杂度：时间 O(n)，空间 O(n)（最坏情况队列存满一层）

BFS 通用模板#

1
from collections import deque
2

3
def bfs(root):
4
    if not root: return 0       # 1. 边界处理
5

6
    queue = deque([root])       # 2. 初始化队列（根据题意决定队列里存什么）
7
    res = ...                   # 3. 初始化返回值
8

9
    while queue:                # 4. 外层循环：队列不空就继续
10
        layer_var = ...         #    每层开始前初始化层级变量
11

12
        for _ in range(len(queue)):  # 5. 内层循环：处理当前层所有节点
13
            node = queue.popleft()
14

15
            if node.left: queue.append(node.left)    # 6. 下一层入队
16
            if node.right: queue.append(node.right)
17

18
            # 7. 处理当前节点（更新层级变量，或提前 return）
19
            ...
20

21
        # 8. for 结束 = 这层处理完，更新返回值
22
        res = ...
23

24
    return res                  # 9. 返回结果

IMPORTANT
BFS 通用模板核心要点
外层 while queue 控制层数，内层 for _ in range(len(queue)) 快照当前层节点数。队列里存什么、每层初始化什么、何时提前 return——这三点决定了模板怎么变形。

两题对比#

步骤	662 最大宽度	111 最小深度
队列存的内容	`(编号, 节点)`	只存节点
每层初始化	`min_seen = inf, max_seen = 0`	无，`depth += 1` 直接加
处理节点	更新 `min_seen / max_seen`	检查是否叶子节点
每层结束后	`ans = max(ans, max_seen - min_seen + 1)`	遇叶子提前 `return`，否则继续

TIP
看到什么题用 BFS

关键词含层、深度、宽度、距离、最近、最短

需要逐层处理，或者找到第一个满足条件的节点就返回

题目涉及从根往下扩散的过程

TIP
队列里存什么
默认只存节点。如果需要额外信息（编号、步数、路径等），就把信息和节点打包成元组一起入队，弹出时解包使用。

TIP
提前 return vs 处理完再 return

找最小/最近：在 for 循环内遇到条件立刻 return，不用等这层全部处理完

找最大/统计全部：等 for 循环结束（整层处理完）再更新结果