1. 考研机试中的树与图论：核心考点与实战策略
作为计算机考研机试的必考内容，树与图论算法占据了近40%的分值比重。去年参加浙大机试时，我在3道树相关题目中栽了跟头，后来复盘发现是因为对非递归遍历和B+树索引等概念理解不够透彻。本文将结合考研真题和力扣高频题型，系统梳理二叉树与图论的12个核心板子题，附带可即插即用的C++实现模板。
提示：机试中的树结构题目往往会在基础算法上增加1-2个变形条件，比如要求用迭代代替递归实现遍历，或在BST查找时附加节点计数功能。
1.1 二叉树的核心知识体系
考研机试对二叉树的考察主要集中在三个维度：
- 结构特性：完全二叉树、满二叉树、BST、AVL树的定义与数学性质
- 遍历算法：前中后序的递归/非递归实现，层次遍历的队列应用
- 应用场景：哈夫曼编码、堆排序、字典树等衍生结构
以2023年北航机试真题为例，题目要求计算二叉树中所有左叶子节点的和。标准解法需要：
int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; stack<TreeNode*> stk; stk.push(root); int sum = 0; while (!stk.empty()) { TreeNode* node = stk.top(); stk.pop(); if (node->left && !node->left->left && !node->left->right) { sum += node->left->val; } if (node->right) stk.push(node->right); if (node->left) stk.push(node->left); } return sum; }这个解法巧妙利用栈实现迭代遍历，同时通过!node->left->left && !node->left->right判断左叶子节点，比递归解法节省了30%的内存空间。
1.2 图论算法的解题框架
图论题目在机试中常以以下形式出现：
- 最短路径：Dijkstra（正权边）、Floyd（多源最短路）
- 连通性判断：Union-Find并查集、Tarjan强连通分量
- 拓扑排序：课程安排、任务调度类问题
清华2022年机试有道题要求计算校园快递站点间的最短配送路径。采用堆优化的Dijkstra算法模板：
vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) { vector<int> dist(graph.size(), INT_MAX); dist[start] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }该实现使用小顶堆保证每次取最小距离节点，时间复杂度优化到O(E + VlogV)。注意d > dist[u]的剪枝判断能避免重复计算，这是很多考生容易忽略的优化点。
2. 二叉树高频题型精讲
2.1 遍历算法的六种实现方式
前序、中序、后序遍历各有递归和迭代两种实现，层次遍历还需掌握自底向上变种。下表对比各实现的特点：
| 遍历方式 | 递归实现 | 迭代实现（栈） | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 前序 | 易写易读 | 需处理右左入栈 | O(n) | O(h) |
| 中序 | 直观 | 需维护当前节点指针 | O(n) | O(h) |
| 后序 | 简单 | 需反向输出或标记访问 | O(n) | O(h) |
| 层次 | 不适合 | 队列+大小记录 | O(n) | O(w) |
其中后序遍历的迭代实现最考验对栈的理解，推荐标记法：
vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<pair<TreeNode*, bool>> stk; stk.push({root, false}); while (!stk.empty()) { auto [node, visited] = stk.top(); stk.pop(); if (!node) continue; if (visited) { res.push_back(node->val); } else { stk.push({node, true}); stk.push({node->right, false}); stk.push({node->left, false}); } } return res; }2.2 二叉搜索树的操作陷阱
BST的查找、插入看似简单，但机试常设置以下陷阱：
- 删除节点：需处理三种情况（无子节点、单子节点、双子节点）
- 验证BST：不能仅比较父节点，要用上下界约束
- 第K小元素：需结合中序遍历计数
例如验证BST的正确写法：
bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } bool helper(TreeNode* node, long lower, long upper) { if (!node) return true; if (node->val <= lower || node->val >= upper) return false; return helper(node->left, lower, node->val) && helper(node->right, node->val, upper); }使用LONG_MIN/MAX避免INT边界值问题，这个细节在考研机试中曾导致30%考生失分。
3. 图论算法实战模板
3.1 最短路径算法的选择策略
根据问题特征选择合适算法：
- 边权非负：Dijkstra（优先队列优化）
- 含负权边：Bellman-Ford（检测负环）
- 全源最短路：Floyd（动态规划思想）
Floyd算法的经典实现：
void floyd(vector<vector<int>>& dist) { int n = dist.size(); for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } }注意初始时dist[i][j]应设为INT_MAX表示不可达，但对角线dist[i][i]=0。
3.2 并查集的路径压缩优化
处理连通性问题时，并查集的两个优化能大幅提升效率：
- 路径压缩：查找时扁平化树结构
- 按秩合并：小树挂在大树下
优化后的并查集模板：
class UnionFind { public: vector<int> parent, rank; UnionFind(int n) : parent(n), rank(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); parent[y] = x; rank[x] += rank[y]; } };在2021年哈工大机试中，使用普通并查集会超时，而优化版能在200ms内处理10^6量级的查询。
4. 机试常见失误与调试技巧
4.1 二叉树操作中的经典错误
- 指针未判空：特别是在递归基线条件中遗漏
if(!root) - 迭代遍历栈溢出：忘记push右子树导致访问违例
- BST验证逻辑缺陷：仅比较父节点与子节点值
调试二叉树问题时，建议打印树的层序结构：
void printTree(TreeNode* root) { queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; ++i) { auto node = q.front(); q.pop(); if (!node) cout << "null "; else { cout << node->val << " "; q.push(node->left); q.push(node->right); } } cout << endl; } }4.2 图论算法的边界处理
- 节点编号：题目是否从0或1开始计数
- 重边处理：保留最小/最大权重边
- 自环检测：是否需要特殊处理
对于邻接表存储，推荐使用vector<vector<pair<int,int>>>结构，既能存边权又方便遍历：
// 添加边示例 vector<vector<pair<int,int>>> graph(n); graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); // 无向图需双向添加 // 遍历邻居示例 for (auto [v, w] : graph[u]) { // 处理u->v的边 }5. 备考建议与资源推荐
5.1 每日训练计划
- 早晨：2道二叉树题（力扣中等难度）
- 下午：1道图论题+1道综合应用题
- 晚上：复盘错题，整理模板
重点训练：
- 二叉树非递归遍历的bug-free实现
- Dijkstra和Floyd的手写速度
- 并查集在复杂场景下的应用
5.2 必刷题目清单
| 类别 | 力扣题号 | 考察重点 |
|---|---|---|
| 二叉树 | 94, 144, 145 | 三种遍历的迭代实现 |
| BST | 98, 450 | 验证与删除操作 |
| 图论 | 743, 207 | Dijkstra与拓扑排序 |
| 并查集 | 684, 547 | 冗余连接与连通分量计数 |
我在最后冲刺阶段发现，反复手写这些模板直到形成肌肉记忆，能在机试时节省至少50%的编码时间。特别是Dijkstra算法，完整实现往往需要15-20行代码，提前准备好模板至关重要。