考研机试必备：二叉树与图论算法实战指南

1. 二叉树与图论在机试中的核心地位考研机试中数据结构和算法永远是重头戏。根据近五年主流高校机试真题统计二叉树相关题目出现频率高达37%图论题目占比约28%。这两大板块共同构成了机试中分值最重的数据结构双雄。我当年备战机试时花了整整两周时间专门打磨这两个模块的解题模板。现在回头看这种针对性训练让我在考场上遇到二叉树层序遍历路径和判断的复合题时能直接套用现成板子节省了至少15分钟调试时间。2. 二叉树高频题型与标准解法2.1 基础遍历三板斧先明确二叉树的三种基础遍历方式前序、中序、后序这是所有衍生题型的基础。以LeetCode 144题为例前序遍历的非递归实现需要重点掌握def preorderTraversal(root): stack, res [root], [] while stack: node stack.pop() if node: res.append(node.val) stack.append(node.right) # 右子树先入栈 stack.append(node.left) return res关键点栈的入栈顺序必须是右子树先于左子树才能保证出栈时左子树优先处理2.2 层序遍历的四种变体层序遍历BFS的模板需要能快速写出以下变体普通层序输出LeetCode 102锯齿形层序LeetCode 103每层最大值LeetCode 515右视图LeetCode 199以锯齿形遍历为例def zigzagLevelOrder(root): if not root: return [] queue deque([root]) res, level [], 0 while queue: size len(queue) tmp [] for _ in range(size): node queue.popleft() tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp[::-1] if level % 2 else tmp) level 1 return res2.3 二叉树重构问题已知两种遍历序列重构二叉树是经典题型需要掌握前序中序LeetCode 105后序中序LeetCode 106层序中序较少见但需了解以前序中序为例的递归解法def buildTree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(preorder[1:1idx], inorder[:idx]) root.right buildTree(preorder[1idx:], inorder[idx1:]) return root3. 图论核心算法模板3.1 最短路径三巨头Dijkstra算法无负权边def dijkstra(graph, start): heap [(0, start)] dist {node: float(inf) for node in graph} dist[start] 0 while heap: d, u heapq.heappop(heap) if d dist[u]: continue for v, w in graph[u].items(): if dist[v] dist[u] w: dist[v] dist[u] w heapq.heappush(heap, (dist[v], v)) return distBellman-Ford含负权边检测def bellman_ford(edges, n, start): dist [float(inf)] * n dist[start] 0 for _ in range(n-1): for u, v, w in edges: if dist[u] w dist[v]: dist[v] dist[u] w # 负权环检测 for u, v, w in edges: if dist[u] w dist[v]: return 存在负权环 return distFloyd-Warshall多源最短路径def floyd_warshall(n, edges): dist [[float(inf)]*n for _ in range(n)] for i in range(n): dist[i][i] 0 for u, v, w in edges: dist[u][v] w for k in range(n): for i in range(n): for j in range(n): dist[i][j] min(dist[i][j], dist[i][k]dist[k][j]) return dist3.2 最小生成树双雄Prim算法邻接矩阵版def prim(matrix): n len(matrix) lowcost [float(inf)] * n closest [0] * n lowcost[0] 0 for i in range(1, n): lowcost[i] matrix[0][i] for _ in range(n-1): min_val float(inf) k 0 for j in range(1, n): if 0 lowcost[j] min_val: min_val lowcost[j] k j for j in range(1, n): if matrix[k][j] lowcost[j]: lowcost[j] matrix[k][j] closest[j] k lowcost[k] 0 return sum(lowcost[1:])Kruskal算法需并查集class UnionFind: def __init__(self, size): self.parent list(range(size)) def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): x_root self.find(x) y_root self.find(y) if x_root ! y_root: self.parent[y_root] x_root def kruskal(edges, n): edges.sort(keylambda x: x[2]) uf UnionFind(n) res 0 for u, v, w in edges: if uf.find(u) ! uf.find(v): uf.union(u, v) res w return res4. 机试实战技巧与避坑指南4.1 输入输出加速技巧机试中常遇到大规模数据输入Python选手需要特别注意import sys input sys.stdin.read # 比input()快10倍以上 data input().split()C选手更应熟记ios::sync_with_stdio(false); cin.tie(nullptr);4.2 常见边界条件检查清单二叉树题目必查空树处理root null单节点树完全倾斜树只有左/右子树图论题目必查零边图只有顶点自环边处理重边取最小值4.3 调试输出技巧在无法使用IDE的考场环境中建议在代码关键位置插入调试输出# 在递归函数开头加入 print(f当前节点: {root.val if root else None}) # 在图算法中加入 print(f处理节点{u}当前距离表: {dist})5. 经典题目组合训练5.1 二叉树综合题[LeetCode 124] 二叉树中的最大路径和[LeetCode 297] 二叉树的序列化与反序列化[LeetCode 437] 路径总和 III前缀和应用5.2 图论综合题[LeetCode 787] K站中转内最便宜的航班Bellman-Ford变种[LeetCode 1584] 连接所有点的最小费用最小生成树[LeetCode 743] 网络延迟时间Dijkstra应用6. 模板代码的个性化改造直接套用模板只能拿到基础分要想脱颖而出需要给算法添加注释说明优化变量命名如dist改为min_dist添加防御性编程检查封装常用操作为辅助函数以Dijkstra算法改造为例def network_delay_time(times, n, k): 返回从节点k出发到所有节点的最大传播时间 graph defaultdict(dict) for u, v, w in times: graph[u][v] w # 构建邻接表 min_dist {i: float(inf) for i in range(1, n1)} min_dist[k] 0 heap [(0, k)] while heap: current_dist, u heapq.heappop(heap) if current_dist min_dist[u]: continue # 已找到更优解 for v, w in graph[u].items(): if min_dist[v] min_dist[u] w: min_dist[v] min_dist[u] w heapq.heappush(heap, (min_dist[v], v)) max_time max(min_dist.values()) return max_time if max_time float(inf) else -1