二叉树基础

什么是二叉树？

二叉树（Binary Tree）是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的定义：

  • 每个节点最多有 2 个子节点
  • 子树有左右之分，不能颠倒
  • 第 i 层最多有 2^(i-1) 个节点
  • 深度为 k 的二叉树最多有 2^k - 1 个节点

二叉树节点定义：

1
2
3
4
5
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

二叉树的性质

  1. 节点数与深度的关系：

    • 第 i 层最多有 2^(i-1) 个节点（i ≥ 1）
    • 深度为 k 的二叉树最多有 2^k - 1 个节点

  2. 叶子节点数：

    • n0 = n2 + 1（n0 为叶子节点数，n2 为度为 2 的节点数）

  3. 完全二叉树的性质：

    • 具有 n 个节点的完全二叉树的深度为 ⌊log₂n⌋ + 1
    • 对于节点 i，其父节点为 ⌊i/2⌋，左子节点为 2i，右子节点为 2i+1

二叉树的类型

1. 满二叉树（Full Binary Tree）

满二叉树是每个节点都有 0 或 2 个子节点的二叉树。

特点：

  • 所有非叶子节点都有 2 个子节点
  • 叶子节点都在最后一层
  • 有 n 个节点的满二叉树的深度为 log₂(n+1)

2. 完全二叉树（Complete Binary Tree）

完全二叉树是除了最后一层外，其他层的节点都是满的，且最后一层的节点都靠左排列。

特点：

  • 适合用数组存储
  • 堆（Heap）就是一种完全二叉树
  • 最后一个非叶子节点的索引为 ⌊n/2⌋

3. 二叉搜索树（Binary Search Tree, BST）

二叉搜索树是一种有序的二叉树，满足以下性质：

  • 左子树所有节点的值 < 根节点的值
  • 右子树所有节点的值 > 根节点的值
  • 左右子树也都是二叉搜索树

优点：

  • 查找、插入、删除的平均时间复杂度为 O(log n)
  • 中序遍历可以得到有序序列

缺点：

  • 最坏情况下（退化为链表）时间复杂度为 O(n)

4. 平衡二叉树（Balanced Binary Tree）

平衡二叉树是任意节点的左右子树高度差的绝对值不超过 1 的二叉树。

常见实现：

  • AVL 树：严格平衡，任意节点左右子树高度差 ≤ 1
  • 红黑树：近似平衡，确保最长路径不超过最短路径的 2 倍

5. B+Tree（B+树）

B+Tree 是一种多路平衡搜索树，是 B-Tree 的变体，广泛应用于数据库索引和文件系统中。

B+Tree 的特点：

  1. 多路平衡树：每个节点可以有多个子节点（通常称为 m 阶 B+Tree）
  2. 所有数据存储在叶子节点：非叶子节点只存储键值（索引）
  3. 叶子节点通过指针连接：形成有序链表，方便范围查询
  4. 所有叶子节点在同一层：保证平衡性

B+Tree 结构示例（3阶）：

1
2
3
4
5
6
                [10, 20]                    (非叶子节点，只存储键值)
               /    |    \
        [5, 8]    [15, 18]    [25, 30]     (非叶子节点)
       /  |  \    /  |  \     /  |  \
[1,3,5] [6,7,8] [10,12,15] [16,17,18] [20,22,25] [28,30,35]
(叶子节点，存储数据)                          (叶子节点通过指针连接)

B+Tree vs B-Tree：

特性 B-Tree B+Tree
数据存储 所有节点都可以存储数据 只有叶子节点存储数据
非叶子节点 存储键值和数据 只存储键值（索引）
叶子节点 不连接 通过指针连接成链表
查找效率 可能在任何层找到数据 必须到叶子节点
范围查询 需要中序遍历 通过链表顺序访问
空间利用率 较低 较高（非叶子节点更小）

B+Tree 的优势：

  1. 适合磁盘存储：

    • 节点大小通常等于磁盘页大小（如 4KB）
    • 减少磁盘 I/O 次数
    • 非叶子节点可以存储更多键值

  2. 范围查询高效：

    • 叶子节点形成有序链表
    • 范围查询只需遍历链表，不需要回溯

  3. 查询稳定：

    • 所有查询都要到叶子节点
    • 查询路径长度相同，性能稳定

B+Tree 的阶数（m）：

  • m 阶 B+Tree：每个节点最多有 m 个子节点
  • 非叶子节点：最多有 m-1 个键值，至少 ⌈m/2⌉ 个键值
  • 叶子节点：最多有 m-1 个数据项，至少 ⌈m/2⌉ 个数据项

B+Tree 操作：

查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def search_bplus_tree(root, key):
    """在B+Tree中查找key"""
    node = root
    
    # 向下查找直到叶子节点
    while not node.is_leaf:
        # 在节点中找到合适的子节点
        i = 0
        while i < len(node.keys) and key >= node.keys[i]:
            i += 1
        node = node.children[i]
    
    # 在叶子节点中查找
    for i, k in enumerate(node.keys):
        if k == key:
            return node.values[i]
    
    return None  # 未找到

插入：

  1. 找到应该插入的叶子节点
  2. 如果叶子节点未满，直接插入
  3. 如果叶子节点已满，进行分裂：
    • 将节点分成两部分
    • 中间键值提升到父节点
    • 如果父节点也满，继续向上分裂

删除：

  1. 找到包含要删除键值的叶子节点
  2. 删除键值
  3. 如果节点键值数量低于最小值，进行合并或借用：
    • 尝试从兄弟节点借用
    • 如果无法借用，与兄弟节点合并

B+Tree 在数据库中的应用：

MySQL InnoDB 中的 B+Tree：

  • 主键索引（聚簇索引）：叶子节点存储完整数据行
  • 辅助索引（非聚簇索引）：叶子节点存储主键值
  • 通常使用 3-4 层的 B+Tree 就可以支持千万级数据

索引结构：

1
2
3
4
5
6
7
8
聚簇索引（主键索引）：
- 叶子节点：存储完整数据行
- 非叶子节点：存储主键值和页指针

辅助索引（二级索引）：
- 叶子节点：存储主键值
- 非叶子节点：存储索引键值和页指针
- 需要回表查询（通过主键值查找完整数据）

B+Tree vs 二叉搜索树：

特性 二叉搜索树 B+Tree
子节点数 最多 2 个 多个（m 个）
高度 O(log n) O(log_m n)，更矮
磁盘 I/O 多 少（节点更大）
范围查询 需要中序遍历 链表顺序访问
适用场景 内存数据结构 磁盘存储、数据库索引

扩展知识点：

  • B-Tree：B+Tree 的前身，所有节点都可以存储数据
  • B*Tree：B+Tree 的变体，非叶子节点之间也有指针连接
  • LSM-Tree：另一种数据库索引结构，适合写多读少场景
  • 哈希索引：适合等值查询，不支持范围查询

6. 堆（Heap）

堆是一种特殊的完全二叉树，满足堆序性质：

  • 大顶堆：父节点的值 ≥ 子节点的值
  • 小顶堆：父节点的值 ≤ 子节点的值

7. 线索二叉树（Threaded Binary Tree）

线索二叉树是在二叉链表的基础上，将空指针域利用起来，指向节点的前驱或后继。

二叉树的遍历

1. 前序遍历（Preorder Traversal）

遍历顺序：根节点 → 左子树 → 右子树

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
def preorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # 访问根节点
        dfs(node.left)           # 遍历左子树
        dfs(node.right)          # 遍历右子树
    
    dfs(root)
    return result

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def preorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # 注意：先压入右节点，再压入左节点
        # 因为栈是后进先出，所以左节点会先出栈
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

2. 中序遍历（Inorder Traversal）

遍历顺序：左子树 → 根节点 → 右子树

特点： 对二叉搜索树进行中序遍历，可以得到有序序列。

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
def inorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # 遍历左子树
        result.append(node.val)  # 访问根节点
        dfs(node.right)          # 遍历右子树
    
    dfs(root)
    return result

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = []
    curr = root
    
    while curr or stack:
        # 一直向左走到底
        while curr:
            stack.append(curr)
            curr = curr.left
        
        # 弹出并访问
        curr = stack.pop()
        result.append(curr.val)
        
        # 转向右子树
        curr = curr.right
    
    return result

3. 后序遍历（Postorder Traversal）

遍历顺序：左子树 → 右子树 → 根节点

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
def postorder_traversal(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # 遍历左子树
        dfs(node.right)          # 遍历右子树
        result.append(node.val)  # 访问根节点
    
    dfs(root)
    return result

迭代实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def postorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # 先压入左节点，再压入右节点
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    # 反转结果（根->右->左 变成 左->右->根）
    return result[::-1]

4. 层序遍历（Level Order Traversal）

层序遍历是按照树的层次，从根节点开始逐层访问节点。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

使用双端队列优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque

def level_order_traversal_optimized(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

二叉树常见操作

1. 求二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def max_depth(root):
    """递归实现"""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def max_depth_iterative(root):
    """迭代实现"""
    if not root:
        return 0
    
    depth = 0
    queue = [root]
    
    while queue:
        depth += 1
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return depth

2. 求二叉树的最小深度

1
2
3
4
5
6
7
8
9
10
11
12
def min_depth(root):
    if not root:
        return 0
    
    # 如果左右子树有一个为空，返回另一个的深度+1
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    
    # 左右子树都存在，返回较小的深度+1
    return 1 + min(min_depth(root.left), min_depth(root.right))

3. 判断是否为相同的二叉树

1
2
3
4
5
6
7
8
def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

4. 判断是否为对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def is_symmetric(root):
    if not root:
        return True
    
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
    
    return is_mirror(root.left, root.right)

5. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def invert_tree(root):
    if not root:
        return None
    
    # 交换左右子树
    root.left, root.right = root.right, root.left
    
    # 递归翻转左右子树
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

def invert_tree_iterative(root):
    """迭代实现"""
    if not root:
        return None
    
    stack = [root]
    
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return root

6. 判断是否为平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def is_balanced(root):
    def get_height(node):
        if not node:
            return 0
        
        left_height = get_height(node.left)
        right_height = get_height(node.right)
        
        # 如果子树不平衡，返回 -1
        if left_height == -1 or right_height == -1:
            return -1
        
        # 如果左右子树高度差大于1，不平衡
        if abs(left_height - right_height) > 1:
            return -1
        
        return 1 + max(left_height, right_height)
    
    return get_height(root) != -1

7. 判断是否为完全二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def is_complete_tree(root):
    if not root:
        return True
    
    queue = [root]
    found_null = False
    
    while queue:
        node = queue.pop(0)
        
        if not node:
            found_null = True
        else:
            # 如果之前已经遇到过空节点，说明不是完全二叉树
            if found_null:
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    return True

二叉搜索树操作

1. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def is_valid_bst(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return validate(node.left, min_val, node.val) and \
               validate(node.right, node.val, max_val)
    
    return validate(root, float('-inf'), float('inf'))

def is_valid_bst_inorder(root):
    """利用中序遍历的特性"""
    prev = None
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        
        if not inorder(node.left):
            return False
        
        if prev is not None and node.val <= prev:
            return False
        
        prev = node.val
        return inorder(node.right)
    
    return inorder(root)

2. 二叉搜索树的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    
    return root

def insert_into_bst_iterative(root, val):
    """迭代实现"""
    if not root:
        return TreeNode(val)
    
    node = root
    while node:
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
                break
            node = node.left
        else:
            if not node.right:
                node.right = TreeNode(val)
                break
            node = node.right
    
    return root

3. 二叉搜索树的删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def delete_node(root, key):
    if not root:
        return None
    
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # 要删除的节点找到了
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        
        # 有两个子节点，找到右子树的最小节点（或左子树的最大节点）
        min_node = get_min(root.right)
        root.val = min_node.val
        root.right = delete_node(root.right, min_node.val)
    
    return root

def get_min(node):
    while node.left:
        node = node.left
    return node

4. 查找二叉搜索树中的节点

1
2
3
4
5
6
7
8
def search_bst(root, val):
    if not root or root.val == val:
        return root
    
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

常见算法题

题1：二叉树的最大路径和

题目描述： 给定一个二叉树，找到路径上节点值的最大和。路径可以从任意节点开始，到任意节点结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def max_path_sum(root):
    max_sum = float('-inf')
    
    def max_gain(node):
        nonlocal max_sum
        
        if not node:
            return 0
        
        # 递归计算左右子树的最大贡献值
        # 如果贡献值为负，则不选择该路径
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        
        # 当前节点的最大路径和
        price_newpath = node.val + left_gain + right_gain
        
        # 更新全局最大值
        max_sum = max(max_sum, price_newpath)
        
        # 返回当前节点的最大贡献值
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum

题2：二叉树的最近公共祖先（LCA）

题目描述： 给定一个二叉树，找到两个节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    # 如果左右子树都找到了，说明当前节点就是LCA
    if left and right:
        return root
    
    # 如果只有一个子树找到了，返回那个结果
    return left if left else right

二叉搜索树的LCA（更简单）：

1
2
3
4
5
6
7
def lowest_common_ancestor_bst(root, p, q):
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor_bst(root.left, p, q)
    elif p.val > root.val and q.val > root.val:
        return lowest_common_ancestor_bst(root.right, p, q)
    else:
        return root

题3：从前序与中序遍历序列构造二叉树

题目描述： 根据前序遍历和中序遍历的结果，构造二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    # 前序遍历的第一个元素是根节点
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    # 在中序遍历中找到根节点的位置
    root_index = inorder.index(root_val)
    
    # 递归构建左右子树
    root.left = build_tree(
        preorder[1:root_index + 1],
        inorder[:root_index]
    )
    root.right = build_tree(
        preorder[root_index + 1:],
        inorder[root_index + 1:]
    )
    
    return root

def build_tree_optimized(preorder, inorder):
    """优化版本：使用哈希表加速查找"""
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = 0
    
    def build(left, right):
        nonlocal pre_idx
        
        if left > right:
            return None
        
        root_val = preorder[pre_idx]
        root = TreeNode(root_val)
        pre_idx += 1
        
        root_index = inorder_map[root_val]
        root.left = build(left, root_index - 1)
        root.right = build(root_index + 1, right)
        
        return root
    
    return build(0, len(inorder) - 1)

题4：从中序与后序遍历序列构造二叉树

题目描述： 根据中序遍历和后序遍历的结果，构造二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def build_tree_from_inorder_postorder(inorder, postorder):
    if not inorder or not postorder:
        return None
    
    # 后序遍历的最后一个元素是根节点
    root_val = postorder[-1]
    root = TreeNode(root_val)
    
    # 在中序遍历中找到根节点的位置
    root_index = inorder.index(root_val)
    
    # 递归构建左右子树
    root.left = build_tree_from_inorder_postorder(
        inorder[:root_index],
        postorder[:root_index]
    )
    root.right = build_tree_from_inorder_postorder(
        inorder[root_index + 1:],
        postorder[root_index:-1]
    )
    
    return root

题5：二叉树的序列化与反序列化

题目描述： 将二叉树序列化为字符串，并能够反序列化回二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def serialize(root):
    """使用前序遍历序列化"""
    if not root:
        return '#'
    
    return str(root.val) + ',' + serialize(root.left) + ',' + serialize(root.right)

def deserialize(data):
    """反序列化"""
    def build():
        val = vals.pop(0)
        if val == '#':
            return None
        
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    
    vals = data.split(',')
    return build()

题6：二叉树的右视图

题目描述： 给定一个二叉树，返回从右侧看到的节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def right_side_view(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        # 获取当前层的最后一个节点
        result.append(queue[-1].val)
        
        size = len(queue)
        for _ in range(size):
            node = queue.pop(0)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

题7：二叉树的锯齿形层序遍历

题目描述： 给定一个二叉树，返回其节点值的锯齿形层序遍历（先从左往右，再从右往左）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def zigzag_level_order(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    left_to_right = True
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        if not left_to_right:
            level.reverse()
        
        result.append(level)
        left_to_right = not left_to_right
    
    return result

题8：路径总和

题目描述： 给定一个二叉树和一个目标和，判断是否存在从根节点到叶子节点的路径，使得路径上所有节点值相加等于目标和。

1
2
3
4
5
6
7
8
9
10
11
def has_path_sum(root, target_sum):
    if not root:
        return False
    
    # 如果是叶子节点，检查是否等于目标和
    if not root.left and not root.right:
        return root.val == target_sum
    
    # 递归检查左右子树
    return has_path_sum(root.left, target_sum - root.val) or \
           has_path_sum(root.right, target_sum - root.val)

题9：路径总和 II

题目描述： 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def path_sum(root, target_sum):
    result = []
    
    def dfs(node, path, remaining):
        if not node:
            return
        
        path.append(node.val)
        remaining -= node.val
        
        # 如果是叶子节点且路径和等于目标和
        if not node.left and not node.right and remaining == 0:
            result.append(path[:])
        
        dfs(node.left, path, remaining)
        dfs(node.right, path, remaining)
        
        # 回溯
        path.pop()
    
    dfs(root, [], target_sum)
    return result

题10：二叉树展开为链表

题目描述： 给定一个二叉树，原地将它展开为一个单链表（前序遍历顺序）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def flatten(root):
    if not root:
        return
    
    # 递归处理左右子树
    flatten(root.left)
    flatten(root.right)
    
    # 保存右子树
    right = root.right
    
    # 将左子树移到右边
    root.right = root.left
    root.left = None
    
    # 找到新右子树的末尾
    curr = root
    while curr.right:
        curr = curr.right
    
    # 将原来的右子树接到末尾
    curr.right = right

题11：填充每个节点的下一个右侧节点指针

题目描述： 给定一个完美二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Node:
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(root):
    if not root:
        return None
    
    leftmost = root
    
    while leftmost.left:
        head = leftmost
        
        while head:
            # 连接1：同一个父节点的左右子节点
            head.left.next = head.right
            
            # 连接2：不同父节点的相邻节点
            if head.next:
                head.right.next = head.next.left
            
            head = head.next
        
        leftmost = leftmost.left
    
    return root

题12：二叉搜索树中的第K小元素

题目描述： 给定一个二叉搜索树，找到其中第 k 小的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def kth_smallest(root, k):
    stack = []
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        
        curr = stack.pop()
        k -= 1
        
        if k == 0:
            return curr.val
        
        curr = curr.right

题13：验证二叉树的前序序列化

题目描述： 给定一个用逗号分隔的字符串，验证它是否是一个正确的二叉树前序序列化。

1
2
3
4
5
6
7
8
9
10
11
12
13
def is_valid_serialization(preorder):
    slots = 1  # 初始化可用槽位数为1（根节点）
    
    for node in preorder.split(','):
        slots -= 1  # 消耗一个槽位
        
        if slots < 0:
            return False
        
        if node != '#':
            slots += 2  # 非空节点增加两个槽位（左右子节点）
    
    return slots == 0

题14：二叉树的层平均值

题目描述： 给定一个二叉树，返回每层的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def average_of_levels(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        level_sum = 0
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            level_sum += node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level_sum / size)
    
    return result

题15：二叉树的最大宽度

题目描述： 给定一个二叉树，返回树的最大宽度（同一层最左和最右节点之间的距离）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def width_of_binary_tree(root):
    if not root:
        return 0
    
    max_width = 0
    queue = [(root, 0)]  # (node, position)
    
    while queue:
        level_size = len(queue)
        _, first_pos = queue[0]
        
        for _ in range(level_size):
            node, pos = queue.pop(0)
            
            if node.left:
                queue.append((node.left, 2 * pos))
            if node.right:
                queue.append((node.right, 2 * pos + 1))
        
        # 计算当前层的宽度
        if queue:
            _, last_pos = queue[-1]
            max_width = max(max_width, last_pos - first_pos + 1)
    
    return max_width

常见面试题

1. 如何判断一个二叉树是否为完全二叉树？

使用层序遍历，如果遇到空节点，则之后不能再有非空节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def is_complete_tree(root):
    if not root:
        return True
    
    queue = [root]
    found_null = False
    
    while queue:
        node = queue.pop(0)
        
        if not node:
            found_null = True
        else:
            if found_null:
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    return True

2. 如何判断一个二叉树是否为满二叉树？

满二叉树满足：节点数 = 2^深度 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_full_tree(root):
    def get_depth_and_count(node):
        if not node:
            return 0, 0
        
        left_depth, left_count = get_depth_and_count(node.left)
        right_depth, right_count = get_depth_and_count(node.right)
        
        depth = 1 + max(left_depth, right_depth)
        count = 1 + left_count + right_count
        
        return depth, count
    
    depth, count = get_depth_and_count(root)
    return count == (1 << depth) - 1

3. 如何求二叉树中两个节点的距离？

先找到最近公共祖先，然后计算两个节点到LCA的距离之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def distance_between_nodes(root, p, q):
    def find_lca(node, p, q):
        if not node or node == p or node == q:
            return node
        
        left = find_lca(node.left, p, q)
        right = find_lca(node.right, p, q)
        
        if left and right:
            return node
        return left if left else right
    
    def get_distance(node, target, dist):
        if not node:
            return -1
        if node == target:
            return dist
        
        left = get_distance(node.left, target, dist + 1)
        if left != -1:
            return left
        
        return get_distance(node.right, target, dist + 1)
    
    lca = find_lca(root, p, q)
    dist1 = get_distance(lca, p, 0)
    dist2 = get_distance(lca, q, 0)
    
    return dist1 + dist2

4. 如何找到二叉树中最深的叶子节点？

使用层序遍历，记录最后一层的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def find_deepest_leaves(root):
    if not root:
        return []
    
    queue = [root]
    
    while queue:
        level = []
        size = len(queue)
        
        for _ in range(size):
            node = queue.pop(0)
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return level

5. 如何统计二叉树中节点的个数？

1
2
3
4
def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

6. 如何统计二叉树中叶子节点的个数？

1
2
3
4
5
6
def count_leaf_nodes(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)

7. 如何找到二叉树中所有路径？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def all_paths(root):
    result = []
    
    def dfs(node, path):
        if not node:
            return
        
        path.append(node.val)
        
        if not node.left and not node.right:
            result.append(path[:])
        else:
            dfs(node.left, path)
            dfs(node.right, path)
        
        path.pop()
    
    dfs(root, [])
    return result

8. 如何判断一个数组是否为二叉搜索树的后序遍历结果？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def verify_postorder(postorder):
    def verify(left, right):
        if left >= right:
            return True
        
        # 后序遍历的最后一个元素是根节点
        root_val = postorder[right]
        
        # 找到左右子树的分界点
        i = left
        while i < right and postorder[i] < root_val:
            i += 1
        
        # 验证右子树的所有元素都大于根节点
        j = i
        while j < right:
            if postorder[j] < root_val:
                return False
            j += 1
        
        # 递归验证左右子树
        return verify(left, i - 1) and verify(i, right - 1)
    
    if not postorder:
        return True
    
    return verify(0, len(postorder) - 1)

总结

核心要点：

  1. 二叉树的基础概念：理解二叉树的结构和性质
  2. 不同类型的二叉树：满二叉树、完全二叉树、二叉搜索树、平衡二叉树等
  3. 遍历方式：前序、中序、后序、层序的递归和迭代实现
  4. 常见操作：求深度、判断类型、翻转、验证等
  5. 算法题：路径和、LCA、序列化、层序遍历变形等

面试重点：

  • 二叉树的遍历（递归和迭代都要掌握）
  • 二叉搜索树的操作和验证
  • 最近公共祖先（LCA）
  • 从遍历序列构造二叉树
  • 路径相关问题
  • 层序遍历及其变形

解题技巧：

  1. 递归思想：大多数二叉树问题都可以用递归解决
  2. 迭代替代递归：使用栈或队列实现迭代
  3. 前序遍历：根→左→右，适合自上而下处理
  4. 后序遍历：左→右→根，适合自下而上处理
  5. 中序遍历：左→根→右，对BST可以得到有序序列
  6. 层序遍历：使用队列，适合按层处理

参考资料：

  • 《算法导论》
  • 《数据结构与算法分析》
  • LeetCode 二叉树专题
  • 《剑指 Offer》