1. 考研机试中的树与图论算法精要作为计算机考研路上的必经关卡机试中的树与图论题目往往让不少同学头疼。不同于日常课程作业机试题目更注重对基础算法的灵活运用和快速实现能力。我在准备某985院校机试时花了两个月时间专项突破树与图论题目最终在机试中获得了前10%的成绩。本文将分享我的备战心得和经过实战检验的代码模板。2. 树结构的基础操作与实现2.1 树节点的标准定义在考研机试中二叉树是最常考察的数据结构。标准的节点定义应该包含以下要素typedef struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} } TreeNode;这个定义采用了C的构造函数初始化方式比纯C风格的struct更简洁。注意在机试环境中某些编译器可能需要加上struct关键字建议提前了解考场环境。2.2 递归遍历的三种形式递归遍历是理解树结构的基础考研中常要求手写遍历代码// 先序遍历 void preorder(TreeNode* root) { if(!root) return; cout root-val ; // 先访问根节点 preorder(root-left); preorder(root-right); } // 中序遍历 void inorder(TreeNode* root) { if(!root) return; inorder(root-left); cout root-val ; // 中间访问根节点 inorder(root-right); } // 后序遍历 void postorder(TreeNode* root) { if(!root) return; postorder(root-left); postorder(root-right); cout root-val ; // 最后访问根节点 }提示递归遍历看似简单但在机试中要注意输出格式如行末空格问题建议使用vector暂存结果再统一输出。3. 迭代遍历的实现技巧3.1 使用栈模拟递归过程递归遍历虽然简洁但在考研机试中面试官可能要求用迭代方式实现。这时需要借助栈来模拟调用过程// 迭代版先序遍历 vectorint preorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; if(root) st.push(root); while(!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if(node-right) st.push(node-right); // 右子节点先入栈 if(node-left) st.push(node-left); // 左子节点后入栈 } return res; }3.2 中序遍历的特殊处理中序遍历的迭代实现较为复杂需要指针辅助vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while(cur || !st.empty()) { if(cur) { // 指针访问到最底层 st.push(cur); cur cur-left; // 左 } else { cur st.top(); // 从栈里弹出的数据就是要处理的数据 st.pop(); res.push_back(cur-val); // 中 cur cur-right; // 右 } } return res; }3.3 后序遍历的取巧方法后序遍历可以利用前序遍历的变种反转vectorint postorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; if(root) st.push(root); while(!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if(node-left) st.push(node-left); // 调整入栈顺序 if(node-right) st.push(node-right); } reverse(res.begin(), res.end()); // 反转结果 return res; }4. 层序遍历及其变种问题4.1 基础层序遍历模板层序遍历是考研高频考点需要使用队列实现vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; queueTreeNode* q; if(root) q.push(root); while(!q.empty()) { int size q.size(); vectorint level; for(int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if(node-left) q.push(node-left); if(node-right) q.push(node-right); } res.push_back(level); } return res; }4.2 典型变种题目解析4.2.1 二叉树的右视图vectorint rightSideView(TreeNode* root) { vectorint res; queueTreeNode* q; if(root) q.push(root); while(!q.empty()) { int size q.size(); for(int i 0; i size; i) { TreeNode* node q.front(); q.pop(); if(i size - 1) res.push_back(node-val); // 每层最后一个节点 if(node-left) q.push(node-left); if(node-right) q.push(node-right); } } return res; }4.2.2 每层最大值vectorint largestValues(TreeNode* root) { vectorint res; queueTreeNode* q; if(root) q.push(root); while(!q.empty()) { int size q.size(); int maxVal INT_MIN; for(int i 0; i size; i) { TreeNode* node q.front(); q.pop(); maxVal max(maxVal, node-val); if(node-left) q.push(node-left); if(node-right) q.push(node-right); } res.push_back(maxVal); } return res; }5. 树结构的经典算法问题5.1 完全二叉树节点计数利用完全二叉树性质优化计算int countNodes(TreeNode* root) { if(!root) return 0; int leftDepth 0, rightDepth 0; TreeNode* left root-left; TreeNode* right root-right; while(left) { // 求左子树深度 left left-left; leftDepth; } while(right) { // 求右子树深度 right right-right; rightDepth; } if(leftDepth rightDepth) { return (2 leftDepth) - 1; // 满二叉树公式 } return countNodes(root-left) countNodes(root-right) 1; }5.2 平衡二叉树判断bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } int getHeight(TreeNode* node) { if(!node) return 0; int left getHeight(node-left); if(left -1) return -1; int right getHeight(node-right); if(right -1) return -1; if(abs(left - right) 1) return -1; return max(left, right) 1; }5.3 从中序和后序序列构造二叉树TreeNode* buildTree(vectorint inorder, vectorint postorder) { if(inorder.empty()) return nullptr; return build(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1); } TreeNode* build(vectorint inorder, int inStart, int inEnd, vectorint postorder, int postStart, int postEnd) { if(inStart inEnd) return nullptr; TreeNode* root new TreeNode(postorder[postEnd]); int rootIndex inStart; while(inorder[rootIndex] ! root-val) rootIndex; int leftSize rootIndex - inStart; root-left build(inorder, inStart, rootIndex-1, postorder, postStart, postStartleftSize-1); root-right build(inorder, rootIndex1, inEnd, postorder, postStartleftSize, postEnd-1); return root; }6. 图论基础算法实现6.1 图的邻接表表示法const int N 1e5 10; vectorint adj[N]; // 邻接表 bool visited[N]; // 访问标记 // 添加边 void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 无向图需要双向添加 }6.2 广度优先搜索(BFS)模板void bfs(int start) { queueint q; q.push(start); visited[start] true; while(!q.empty()) { int u q.front(); q.pop(); for(int v : adj[u]) { if(!visited[v]) { visited[v] true; q.push(v); } } } }6.3 Dijkstra最短路径算法6.3.1 朴素版实现const int INF 0x3f3f3f3f; int dist[N]; bool st[N]; int dijkstra(int n, int start) { memset(dist, 0x3f, sizeof dist); dist[start] 0; for(int i 0; i n; i) { int t -1; for(int j 1; j n; j) { if(!st[j] (t -1 || dist[j] dist[t])) t j; } st[t] true; for(int j 1; j n; j) { dist[j] min(dist[j], dist[t] g[t][j]); } } return dist[n] INF ? -1 : dist[n]; }6.3.2 堆优化版本typedef pairint, int PII; priority_queuePII, vectorPII, greaterPII heap; int dijkstra(int n, int start) { memset(dist, 0x3f, sizeof dist); dist[start] 0; heap.push({0, start}); while(!heap.empty()) { auto t heap.top(); heap.pop(); int ver t.second, distance t.first; if(st[ver]) continue; st[ver] true; for(int i h[ver]; i ! -1; i ne[i]) { int j e[i]; if(dist[j] distance w[i]) { dist[j] distance w[i]; heap.push({dist[j], j}); } } } return dist[n] INF ? -1 : dist[n]; }7. 考研机试的实战建议在最后的冲刺阶段我总结了三点关键经验模板代码要熟练将上述算法模板手写练习至少10遍直到能够闭眼写出无语法错误的代码。考场上的时间压力很大没有时间慢慢调试。边界条件要重视空树、单节点树、链式树等特殊情况要单独测试。机试评分往往有隐藏的边界测试用例。调试技巧要掌握学会使用print调试法在关键位置输出中间变量值。考场环境可能没有熟悉的IDE要适应原始调试方式。注意不同院校的机试风格差异很大建议至少做3套目标院校的往年真题了解其命题偏好和难度水平。
