数据结构套路实战：堆、哈希、二叉树在题目中的高频用法

在算法面试与考题中，堆（Heap）、哈希表（Hash Table）和二叉树（Binary Tree） 堪称三大“万金油”数据结构。它们拥有独特的性质，能高效解决特定模式的问题。

一、堆（Heap）：动态极值维护的利器

堆的核心能力：高效维护动态数据集的最大值或最小值，时间复杂度为 O(log n) 的插入/删除，O(1) 的极值访问。

堆（Heap）结构示意图

高频场景 1：Top K 问题

• 问题模式： 从海量数据中找出最大/最小的 K 个元素。
• 堆解法：
  • 找最大 K 个： 维护一个最小堆，堆顶是当前 K 个元素中最小的。新元素比堆顶大时，替换堆顶并调整堆。
  • 找最小 K 个： 维护一个最大堆，堆顶是当前 K 个元素中最大的。新元素比堆顶小时，替换堆顶并调整堆。
• 时间复杂度： O(n log K)，远优于 O(n log n) 的全局排序。
• 经典例题：
  • LeetCode 215: 数组中的第 K 个最大元素
  • LeetCode 347: 前 K 个高频元素 (结合哈希表计数)
  • LeetCode 973: 最接近原点的 K 个点
• 模板代码 (Python - 最小堆找最大 K 个):

import heapq

def top_k_largest(nums, k):
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        else:
            if num > min_heap[0]:  # 比最小堆的堆顶大
                heapq.heappop(min_heap)
                heapq.heappush(min_heap, num)
    return min_heap  # 此时堆中是最大的K个元素，堆顶是第K大

堆在Top K问题中的应用

高频场景 2：流式数据的中位数

• 问题模式： 数据持续流入，需要随时知道当前所有数据的中位数。
• 堆解法 (双堆法)：
  • 维护两个堆：一个最大堆 (left_heap) 存放较小的一半数，一个最小堆 (right_heap) 存放较大的一半数。
  • 保证 len(left_heap) == len(right_heap) 或 len(left_heap) == len(right_heap) + 1。
  • 中位数计算：
    • 总数偶数：( -left_heap[0] + right_heap[0]) / 2.0 (最大堆堆顶取负)
    • 总数奇数：-left_heap[0]
  • 插入策略：
    1. 新数 num 插入 left_heap (需取负用 heapq.heappush 模拟最大堆)。
    2. 将 left_heap 的堆顶（实际最大值）弹出并插入 right_heap。
    3. 如果此时 len(left_heap) < len(right_heap)，将 right_heap 堆顶（最小值）弹出并插入 left_heap。 双堆求中位数原理

• 经典例题： LeetCode 295: 数据流的中位数
• 模板代码 (Python)：

import heapq

class MedianFinder:
    def __init__(self):
        self.left = []  # 最大堆 (用负数模拟)
        self.right = [] # 最小堆

    def addNum(self, num: int) -> None:
        heapq.heappush(self.left, -num)  # 先放入左堆
        max_left = -heapq.heappop(self.left)  # 取出左堆最大值
        heapq.heappush(self.right, max_left)  # 放入右堆
        if len(self.right) > len(self.left):  # 保证左堆元素数 >= 右堆
            min_right = heapq.heappop(self.right)
            heapq.heappush(self.left, -min_right)

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]
        return (-self.left[0] + self.right[0]) / 2.0

高频场景 3：利用堆优化贪心/搜索

• 问题模式： 在需要不断选择当前“最优”选项的贪心策略中，或在 BFS 搜索中需要按特定优先级（如代价最小）出队。
• 堆解法：
  • 贪心： 用堆维护当前所有可选项，每次取堆顶（最优项）进行操作，并动态更新堆。
  • Dijkstra 算法： 使用优先队列（最小堆） 存储 (distance, node)，每次从堆中取出当前距离最小的节点进行松弛操作。这是堆在图论中的核心应用。
  • A 搜索：* 使用优先队列存储 (f_score = g_score + h_score, node)，按 f_score 出队。
• 经典例题：
  • LeetCode 253: 会议室 II (按开始时间排序 + 最小堆维护最早结束时间)
  • LeetCode 23: 合并 K 个升序链表 (最小堆维护 K 个链表头节点)
  • LeetCode 630: 课程表 III (按截止日期排序 + 最大堆维护已选课程持续时间)
  • 所有需要 Dijkstra 或 A* 的图论问题 (如 LeetCode 743, 1514)。

二、哈希表（Hash Table）：快速查找与状态记录的基石

哈希表的核心能力：基于键（Key）的 O(1) 平均时间复杂度的插入、删除和查找。用于快速存取和记录状态。

高频场景 1：快速查找与计数

• 问题模式：
  • 判断元素是否存在。
  • 统计元素出现次数。
  • 记录元素及其相关信息（索引、状态等）。
• 哈希解法：
  • 使用 dict (Python) / HashMap (Java) / unordered_map (C++)。
  • 计数： freq_map[num] = freq_map.get(num, 0) + 1
  • 存在性/索引记录： index_map[element] = index 或 set 存储元素。
• 经典例题：
  • LeetCode 1: 两数之和 (用 dict 记录 {target - num: index})
  • LeetCode 136: 只出现一次的数字 (异或或哈希计数)
  • LeetCode 242: 有效的字母异位词 (统计两字符串字符频率是否相同)
  • LeetCode 349: 两个数组的交集 (使用 set)

高频场景 2：子数组/子串相关问题

• 问题模式：
  • 寻找和为特定值（如 K、0）的连续子数组。
  • 寻找包含特定元素（如所有字符、至多 K 个不同字符）的最长/最短连续子数组/子串。
• 哈希解法（核心：前缀和 + 哈希）：
  • 计算数组的前缀和数组 prefix (prefix[i] = nums[0] + nums[1] + ... + nums[i-1])。
  • 寻找和为 K 的子数组： prefix[j] - prefix[i] = K => prefix[j] = prefix[i] + K。遍历时，用哈希表记录 {当前前缀和值: 出现次数/最早出现索引}。对于当前 prefix[j]，查找 prefix[j] - K 是否在哈希表中。
  • 滑动窗口 + 哈希计数： 维护窗口内元素的哈希计数。根据窗口条件（如不同字符数 <= K）移动左右指针，更新哈希表和结果。
• 经典例题：
  • LeetCode 560: 和为 K 的子数组 (前缀和 + 哈希计数)
  • LeetCode 1248: 统计「优美子数组」 (奇偶转换 + 前缀和 + 哈希)
  • LeetCode 3: 无重复字符的最长子串 (滑动窗口 + set 或 dict 记录字符最新位置)
  • LeetCode 76: 最小覆盖子串 (滑动窗口 + dict 记录目标字符需求)
  • LeetCode 992: K 个不同整数的子数组 (滑动窗口 + dict 计数)

高频场景 3：状态记录与去重

• 问题模式：
  • 避免重复计算（Memoization）。
  • 记录访问过的状态（如 BFS/DFS 中的 visited）。
  • 快速判断状态是否重复或等价。
• 哈希解法：
  • Memoization： 用哈希表缓存函数参数与计算结果的映射。常用于递归优化（动态规划）。
  • BFS/DFS visited： 用 set 或 dict 存储已访问的节点（状态）。状态的表示是关键（坐标、序列化字符串、位图等）。
  • 状态压缩： 将复杂状态（如数组、集合）映射成一个简单的 Key（如元组、字符串、整数位掩码）存储在哈希表中。
• 经典例题：
  • 任何需要 Memoization 的递归问题 (如 LeetCode 70, 198, 斐波那契等)。
  • LeetCode 127: 单词接龙 (BFS + visited set 记录已访问单词)。
  • LeetCode 752: 打开转盘锁 (BFS + visited set 记录已访问密码)。
  • LeetCode 37: 解数独 / LeetCode 51: N 皇后 (DFS + 用数组或位运算记录行列块状态，状态可看作一种压缩)。
  • LeetCode 128: 最长连续序列 (用 set 存储所有数字，快速查找 num+1)。

高频场景 4：映射与分组

• 问题模式：
  • 根据某个键（Key）将元素分组。
  • 建立元素间的映射关系。
• 哈希解法： defaultdict(list) 或 defaultdict(set) 是最常用的分组工具。
• 经典例题：
  • LeetCode 49: 字母异位词分组 (将单词按排序后的字符串分组)。
  • LeetCode 350: 两个数组的交集 II (记录 nums1 中元素频率，遍历 nums2 匹配)。
  • LeetCode 811: 子域名访问计数 (分割域名，逐级累加计数)。

三、二叉树（Binary Tree）：递归与遍历的艺术

二叉树是递归定义的天然载体，其遍历（前序、中序、后序、层序）是解决相关问题的基础框架。

高频场景 1：深度优先搜索（DFS） - 递归与迭代

• 核心： 递归或使用栈模拟递归过程。
• 三种基本遍历：
  • 前序遍历 (Preorder)： 根 -> 左 -> 右 (常用于树的复制、序列化、前缀表达式)。
  • 中序遍历 (Inorder)： 左 -> 根 -> 右 (二叉搜索树 BST 得到升序序列！)。
  • 后序遍历 (Postorder)： 左 -> 右 -> 根 (常用于计算子树信息、释放树、后缀表达式)。
• 递归模板 (Python)：

def dfs(root: TreeNode):
    if not root: return  # 递归终止条件
    # 前序遍历位置 (操作 root.val)
    dfs(root.left)      # 递归左子树
    # 中序遍历位置 (操作 root.val)
    dfs(root.right)     # 递归右子树
    # 后序遍历位置 (操作 root.val)

• 迭代模板 (前序 - Python)：

def preorderTraversal(root: TreeNode) -> List[int]:
    if not root: return []
    stack, res = [root], []
    while stack:
        node = stack.pop()
        res.append(node.val)  # 访问根
        if node.right: stack.append(node.right)  # 右先入后出
        if node.left: stack.append(node.left)    # 左后入先出
    return res

• 经典例题：
  • LeetCode 144: 二叉树的前序遍历
  • LeetCode 94: 二叉树的中序遍历
  • LeetCode 145: 二叉树的后序遍历
  • LeetCode 104: 二叉树的最大深度 (后序遍历)
  • LeetCode 101: 对称二叉树 (同时递归左右子树)
  • LeetCode 226: 翻转二叉树 (前序或后序遍历)

高频场景 2：广度优先搜索（BFS） - 层序遍历

• 核心： 使用队列（Queue）按层处理节点。
• 模板代码 (Python)：

from collections import deque

def levelOrder(root: TreeNode) -> List[List[int]]:
    if not root: return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):  # 处理当前层所有节点
            node = queue.popleft()
            current_level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(current_level)  # 添加当前层结果
    return result

• 应用：
  • 求树的层数/高度（BFS 层数）。
  • 求每层的最大值/平均值。
  • 找到从根节点到叶节点的最短路径（BFS 首次到达叶节点）。
  • 序列化/反序列化二叉树（按层存储）。
• 经典例题：
  • LeetCode 102: 二叉树的层序遍历
  • LeetCode 107: 二叉树的层序遍历 II (自底向上)
  • LeetCode 199: 二叉树的右视图 (记录每层最后一个节点)
  • LeetCode 513: 找树左下角的值 (BFS 记录每层第一个节点)

高频场景 3：二叉搜索树（BST）的特性应用

• 核心特性： 中序遍历结果是升序序列。左子树 < 根 < 右子树。
• 高频操作：
  • 验证 BST： 中序遍历，检查是否严格递增。或递归传递值范围约束。
  • 搜索： 利用 BST 性质二分查找。
  • 插入： 递归/迭代找到合适位置插入新节点。
  • 删除： 分情况处理（叶子节点、单子节点、双子节点 - 找前驱或后继替换）。
  • 利用中序性质：
    • LeetCode 230: 二叉搜索树中第 K 小的元素 (中序遍历到第 K 个)。
    • LeetCode 530: 二叉搜索树的最小绝对差 / LeetCode 783: 二叉搜索树节点最小距离 (中序遍历相邻节点差最小值)。
    • LeetCode 98: 验证二叉搜索树 (中序遍历检查递增)。
    • LeetCode 538 / 1038: 把二叉搜索树转换为累加树 (逆中序遍历 - 右根左，累加和)。
• BST 搜索模板 (递归)：

def searchBST(root: TreeNode, val: int) -> TreeNode:
    if not root or root.val == val:
        return root
    if val < root.val:
        return searchBST(root.left, val)
    else:
        return searchBST(root.right, val)

二叉树遍历方式对比

高频场景 4：树形动态规划（Tree DP）

• 问题模式： 树的问题中，一个节点的解需要用到其左右子树的解。
• 解法： 通常采用后序遍历（先处理左右子树，再处理根节点）。设计递归函数 dfs(node) 返回以 node 为根的子树相关的状态信息。
• 经典例题：
  • LeetCode 124: 二叉树中的最大路径和 (dfs(node) 返回该节点能向上贡献的最大路径和，同时更新全局最大路径和)。
  • LeetCode 337: 打家劫舍 III (dfs(node) 返回 [偷node的最大收益, 不偷node的最大收益] )。
  • LeetCode 543: 二叉树的直径 (dfs(node) 返回以 node 为根的树的最大深度，同时更新经过 node 的最长路径即 L深度 + R深度 )。
• 模板思想：

def dfs(node):
    if not node: return base_case  # 空节点基本情况
    left_info = dfs(node.left)     # 获取左子树信息
    right_info = dfs(node.right)   # 获取右子树信息
    # 利用 left_info 和 right_info 计算以 node 为根的树的信息
    current_info = ... 
    # 可能更新全局结果 (如最大路径和、最长直径)
    return current_info

高频场景 5：最近公共祖先（LCA）

• 问题模式： 求二叉树中两个节点 p 和 q 的最近公共祖先。
• 高效解法 (后序遍历)：
  1. 如果 root 为空，或 root 等于 p 或 q，直接返回 root。
  2. 递归在左子树中查找：left = LCA(root.left, p, q)
  3. 递归在右子树中查找：right = LCA(root.right, p, q)
  4. 关键逻辑：
     • 如果 left 和 right 都非空：说明 p 和 q 分别在 root 的两侧，root 就是 LCA。
     • 如果 left 非空，right 为空：说明 LCA 在左子树中，返回 left。
     • 如果 right 非空，left 为空：说明 LCA 在右子树中，返回 right。
     • 如果都为空：返回 None。
• 经典例题： LeetCode 236: 二叉树的最近公共祖先
• 模板代码 (Python)：

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:  # p 和 q 分列 root 两侧
        return root
    return left if left else right  # 返回非空的那个，或者 None

高频场景 6：Morris 遍历（进阶）

• 核心思想： 利用树中大量空闲的叶节点右指针，实现 O(1) 额外空间复杂度的中序遍历（或其他遍历）。
• 步骤 (中序)：
  1. 初始化当前节点 cur = root。
  2. 当 cur 不为空：
     • 如果 cur 没有左孩子：
       • 访问 cur。
       • cur = cur.right。
     • 如果 cur 有左孩子：
       • 找到 cur 左子树上的最右节点 pre（即 cur 的中序遍历前驱节点）。
         • 如果 pre.right 为空：
         • 将 pre.right 指向 cur (建立线索)。
         • cur = cur.left。
         • 如果 pre.right 指向 cur (说明已建立线索且左子树已访问完)：
         • 断开线索：pre.right = None。
         • 访问 cur。
         • cur = cur.right。
• 应用场景： 对空间复杂度有严格 O(1) 要求的情况（通常面试不强制要求，但了解有加分）。
• 经典例题： LeetCode 94: 二叉树的中序遍历 (要求 O(1) 空间)。

四、综合应用：数据结构组合拳

许多复杂问题需要结合多种数据结构协同解决。

组合案例 1：LFU 缓存 (LeetCode 460)

• 需求： 设计缓存，当容量满时淘汰最不经常使用（访问次数最小）的键。访问次数相同时，淘汰最久未使用的键。
• 数据结构组合：
  1. 哈希表 key_to_val_freq： {key: (value, freq)}，O(1) 获取值及其频率。
  2. 哈希表 freq_to_keys： {freq: OrderedDict/LinkedHashSet}，记录每个频率对应的键集合，该集合能快速删除最久未使用的键（链表特性）。通常用 defaultdict(OrderedDict) 或自定义双向链表实现 LRU。
  3. 最小频率变量 min_freq： 快速定位当前最低频率。
• 核心操作 (get, put) 思路：
  • get(key)：
    1. 从 key_to_val_freq 获取 value 和旧频率 freq。不存在返回 -1。
    2. 在 freq_to_keys[freq] 中删除 key。如果删除后该频率链表为空且 freq == min_freq，则 min_freq++。
    3. 更新 key 的频率为 freq + 1。
    4. 将 key 添加到 freq_to_keys[freq + 1] 链表的最新位置（尾部）。
    5. 更新 key_to_val_freq[key] = (value, freq+1)。
    6. 返回 value。
  • put(key, value)：
    1. 如果容量为 0，直接返回。
    2. 如果 key 已存在，更新 value，并执行一次 get(key) 更新频率和位置。
    3. 如果 key 不存在：
       • 如果缓存已满：
         1. 从 freq_to_keys[min_freq] 中删除最久未使用的键（链表头部）。
         2. 从 key_to_val_freq 中删除该键。
       • 添加新键 key：
         • min_freq = 1 (新键频率为 1)。
         • 将 key 添加到 freq_to_keys[1] 的尾部。
         • key_to_val_freq[key] = (value, 1)。

组合案例 2：设计推特 Timeline (LeetCode 355)

• 需求： 用户发推文、关注/取关、获取最近 10 条推文（自己 + 关注的人，按时间逆序）。
• 数据结构组合：
  1. 全局时间戳 timestamp： 为每条推文分配唯一递增 ID（或直接存储时间戳）。
  2. 用户表 user_map： {userId: User}。
  3. User 类包含：
     • user_id
     • followed (set): 关注的人 ID 集合。
     • tweets (LinkedList / list): 该用户发布的推文链表（节点存储 tweet_id, timestamp）。
  4. 推文获取优化： 合并 K 个有序链表（用户自己 + 关注的人的推文链表）取前 10 条。
     • 使用 最大堆（优先队列）：存储 (timestamp, tweet_id, user_id, tweet_index)。tweet_index 指向该用户下一条要合并的推文索引。
• 核心操作：
  • postTweet(userId, tweetId)：创建推文对象（tweetId, 当前timestamp++），添加到相应用户的 tweets 链表头部。
  • getNewsFeed(userId)：
    1. 获取用户自己及其所有关注者的 tweets 链表头节点（最新推文）。
    2. 将这些头节点（如果存在）加入最大堆（按 timestamp 排序）。
    3. 弹出堆顶（最新推文）加入结果。
    4. 如果该推文所属用户还有下一条推文（tweet_index + 1），将其加入堆。
    5. 重复步骤 3-4，直到取满 10 条或堆为空。
  • follow(followerId, followeeId)：followerId 的 followed 集合加入 followeeId。
  • unfollow(followerId, followeeId)：followerId 的 followed 集合移除 followeeId (如果存在)。

五、识别题目中的数据结构“信号词”

• 堆 (Heap / PriorityQueue)：
  • “最大/最小的 K 个”、“第 K 大/小”、“最接近的 K 个”。
  • “高频”、“经常”、“Top K”。
  • “实时中位数”、“不断输入/流数据”。
  • “合并 K 个有序序列”。
  • “贪心” + “动态选择最优”。
  • “最短路径”、“最少成本” (Dijkstra)。
• 哈希表 (Hash / Map / Dict / Set)：
  • “快速查找”、“是否存在”、“记录位置/状态”。
  • “计数”、“频率”、“出现次数”。
  • “唯一”、“重复”、“去重”。
  • “映射关系”、“分组”、“归类”。
  • “子数组和”、“连续子数组”、“连续子串”。
  • “记忆化”、“缓存”、“避免重复计算”。
  • “状态记录”、“访问标记” (visited)。
• 二叉树 (Binary Tree)：
  • 题目直接给出二叉树结构。
  • “层次”、“按层”、“深度”、“宽度”。
  • “路径”、“根到叶”、“祖先”。
  • “遍历”、“前序”、“中序”、“后序”。
  • “镜像”、“对称”、“翻转”。
  • “二叉搜索树 (BST)”、“有序”、“排序”、“第 K 小”、“范围查询”、“验证 BST”。
  • “子树”、“最大/最小深度”、“平衡”。
  • “最近公共祖先 (LCA)”。
  • “序列化”、“反序列化”。