1. 项目概述从一道经典面试题说起最近在帮团队做算法内训又翻出了“二叉树的垂直总和”这道题。说实话第一次看到这个题目时我也愣了一下垂直总和听起来有点抽象。但仔细一想这不就是把二叉树这个二维结构按照水平距离列号重新投影到一维数组上然后对同一列的所有节点值求和嘛。这个算法在考察候选人对于二叉树遍历、数据结构映射以及边界情况处理上是个非常不错的切入点。它不像单纯的遍历那么直白也不像动态规划那么烧脑属于那种“懂了就很简单没想通就卡壳”的典型问题。在实际场景中这类“按列聚合”的思想其实挺常见的。比如在图形化展示树状结构数据时我们可能需要计算每一列或每一层的某些统计值总和、平均值、最大值用于生成图表又或者在处理一些具有隐含坐标的布局问题时快速获取某一垂直方向上的属性汇总。理解了这个算法你不仅能够解决一道具体的题目更能掌握一种将树形结构进行“空间坐标化”并进行聚合分析的通用思路。无论你是正在准备面试的校招生还是想巩固基础的在职工程师吃透这个算法都大有裨益。接下来我将从问题定义、核心思路、代码实现到优化技巧为你完整拆解。2. 核心思路与算法设计2.1 问题重述与关键定义首先我们必须明确“垂直总和”到底在算什么。给定一棵二叉树我们为每个节点赋予一个“水平距离”Horizontal Distance, 简称HD。这个距离是一个整数坐标定义如下根节点的HD为0。如果一个节点的HD是d那么其左子节点的HD为d - 1。如果一个节点的HD是d那么其右子节点的HD为d 1。“垂直总和”就是指所有具有相同HD值的节点其节点值之和。我们的目标就是计算出所有HD值对应的垂直总和。举个例子假设我们有如下二叉树括号内为节点值1(1) / \ 2(2) 3(3) / \ \ 4(4) 5(5) 6(6)根据HD定义节点1根: HD 0节点21的左子: HD 0 - 1 -1节点31的右子: HD 0 1 1节点42的左子: HD -1 - 1 -2节点52的右子: HD -1 1 0节点63的右子: HD 1 1 2那么垂直总和为HD -2: 只有节点4总和为4。HD -1: 只有节点2总和为2。HD 0: 节点1和节点5总和为1 5 6。HD 1: 节点3总和为3。HD 2: 节点6总和为6。所以输出应该是一个包含这些和的列表通常按照HD从小到大的顺序排列[4, 2, 6, 3, 6]。2.2 算法选型为什么是“哈希表遍历”看到这个问题最直接的思路就是模拟上述过程遍历每个节点计算其HD然后把节点值累加到对应HD的“桶”里。这里有两个核心子问题如何遍历树前序、中序、后序还是层序答案是都可以。因为计算每个节点的HD并不依赖于其子节点或兄弟节点的处理结果HD只由父节点和左右方向决定所以任何一种遍历方式都能访问到所有节点。层序遍历BFS在直觉上更贴近“垂直”的视觉概念但DFS代码通常更简洁。我们选择使用前序遍历DFS因为它递归实现起来非常直观。如何存储和累加不同HD的和我们需要一个数据结构能够根据HD作为键快速找到对应的累加和作为值并进行加法操作。数组似乎不行因为HD可能是负数且范围不确定。此时哈希表在C中是std::map或std::unordered_map就成了不二之选。它提供了O(1)平均时间复杂度的查找和插入完美契合需求。因此主流且高效的算法框架就是深度优先搜索DFS遍历 哈希表记录各HD的和。算法时间复杂度是O(N)其中N是节点数因为每个节点访问一次空间复杂度在最坏情况下树退化成链表是O(N)用于存储递归调用栈和哈希表。注意这里有一个常见的思维陷阱。有人可能会想先计算树的最大最小HD来确定数组大小再用数组存储。这需要两次遍历并不比哈希表一次遍历更优。哈希表方案在代码简洁性和效率上通常是更好的选择。2.3 数据结构设计mapvsunordered_map在C中我们有两个主要的哈希表选择std::map和std::unordered_map。std::map基于红黑树实现键值对按键排序。插入、删除、查找的时间复杂度是O(log n)。std::unordered_map基于哈希表实现键值对无序。平均情况下插入、删除、查找的时间复杂度是O(1)最坏情况O(n)。对于本题选择哪一个如果最终结果需要按HD顺序输出那么使用std::map是更便利的因为它内部已经排好序我们只需要顺序遍历输出即可。虽然O(log n)的每次操作比unordered_map的O(1)慢但对于节点数N在合理范围内比如几千几万这个差异微乎其微代码却更简洁。如果只关心总和不关心顺序或者愿意在最后单独排序那么std::unordered_map在理论上平均速度更快。考虑到输出需要有序且为了代码的清晰易懂在本详解中我们将使用std::mapint, int。键key是水平距离HD值value是该HD上所有节点值的累加和。3. 深度优先搜索DFS递归实现详解3.1 递归函数的设计与参数传递递归是解决树问题的利器。我们需要设计一个递归函数它负责处理以当前节点为根的一棵子树。这个函数需要知道当前节点TreeNode* node指向正在处理的节点。当前节点的水平距离int hd这个值从父节点传递而来。存储结果的哈希表std::mapint, int verticalSum需要以引用方式传递确保所有递归调用修改的是同一个映射表。函数原型可以定义为void calculateVerticalSum(TreeNode* node, int hd, std::mapint, int verticalSum) { if (node nullptr) { return; // 基准情况空节点直接返回 } // 核心操作将当前节点值累加到其HD对应的总和上 verticalSum[hd] node-val; // 递归处理左子树和右子树 calculateVerticalSum(node-left, hd - 1, verticalSum); calculateVerticalSum(node-right, hd 1, verticalSum); }3.2 递归过程的模拟与栈帧分析让我们用之前那棵二叉树来模拟一下递归调用栈这能帮你彻底理解执行流程。假设树节点定义如下struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };调用calculateVerticalSum(root, 0, verticalSum)。调用1node1, hd0。verticalSum[0] 1-verticalSum[0] 1。然后发起调用2:calculateVerticalSum(节点2, 0-1, ...)-hd -1调用2完成后调用3:calculateVerticalSum(节点3, 01, ...)-hd 1调用2node2, hd-1。verticalSum[-1] 2-verticalSum[-1] 2。然后发起调用4:calculateVerticalSum(节点4, -1-1, ...)-hd -2调用4完成后调用5:calculateVerticalSum(节点5, -11, ...)-hd 0调用4node4, hd-2。verticalSum[-2] 4-verticalSum[-2] 4。节点4无左右孩子调用4结束返回到调用2。调用5node5, hd0。verticalSum[0] 5-verticalSum[0] 1 5 6。节点5无左右孩子调用5结束返回到调用2。调用2结束返回到调用1。调用3node3, hd1。verticalSum[1] 3-verticalSum[1] 3。然后发起调用6:calculateVerticalSum(节点6, 11, ...)-hd 2调用6node6, hd2。verticalSum[2] 6-verticalSum[2] 6。节点6无左右孩子调用6结束返回到调用3。调用3结束返回到调用1。调用1结束整个递归完成。最终verticalSum这个map中的内容就是{-2:4, -1:2, 0:6, 1:3, 2:6}。3.3 边界条件与递归终止递归必须有一个明确的终止条件否则会无限进行下去导致栈溢出。对于树遍历终止条件就是访问到空节点nullptr。在函数开始处判断if (node nullptr) return;这就是递归的“基准情况”。它确保了当遍历到叶子节点的子节点为空时递归调用会停止并返回。实操心得在处理树递归时把nullptr判断放在函数开头是一个好习惯这能让代码逻辑更清晰避免在函数内部多次判断左右子节点是否可访问。这也被称为“卫语句”风格。4. 层序遍历BFS迭代实现解析虽然DFS递归很简洁但有时我们可能希望使用迭代来避免递归深度过大可能导致的栈溢出问题尽管对于平衡二叉树这很少见或者就是想用迭代逻辑来练习。层序遍历BFS的迭代实现是另一种直观的方案。4.1 迭代算法的核心队列与节点信息打包在BFS中我们使用队列。但队列里不能只存节点指针还需要存储该节点对应的水平距离HD。因此我们需要将两者“打包”在一起。在C中最方便的方式是使用std::queuestd::pairTreeNode*, int即队列的每个元素是一个对子pair包含节点指针和其HD。算法步骤如下创建结果mapverticalSum和一个队列q。将根节点及其HD0作为pair入队。当队列不为空时循环 a. 出队一个元素得到当前节点currNode和其HDcurrHd。 b. 将currNode-val累加到verticalSum[currHd]。 c. 如果currNode有左子节点将(左子节点, currHd - 1)入队。 d. 如果currNode有右子节点将(右子节点, currHd 1)入队。循环结束verticalSum中即为所求。4.2 BFS实现代码与DFS对比std::mapint, int getVerticalSumBFS(TreeNode* root) { std::mapint, int verticalSum; if (root nullptr) return verticalSum; // 处理空树 std::queuestd::pairTreeNode*, int q; q.push({root, 0}); // 根节点HD为0 while (!q.empty()) { auto [node, hd] q.front(); // C17结构化绑定清晰获取节点和HD q.pop(); verticalSum[hd] node-val; if (node-left ! nullptr) { q.push({node-left, hd - 1}); } if (node-right ! nullptr) { q.push({node-right, hd 1}); } } return verticalSum; }DFS递归 vs BFS迭代对比代码简洁性DFS递归通常更短逻辑更贴近问题定义“先处理自己再处理左右”。空间复杂度在最坏情况下树退化成链表DFS递归的空间复杂度是O(N)调用栈BFS迭代的空间复杂度也是O(N)队列。但BFS的空间消耗是宽度决定的对于平衡二叉树BFS队列可能同时存储较多节点而DFS递归深度是树高O(log N)。适用场景如果树非常深担心递归栈溢出或者问题本身更适合逐层处理比如需要记录每层信息BFS是更好的选择。对于本题两者皆可DFS更常用。注意事项使用BFS时注意队列中pair元素的顺序第一个是节点指针第二个是HD入队出队时要对应。利用C17的结构化绑定auto [node, hd]可以极大提高代码可读性。5. 完整可运行源码及测试用例5.1 二叉树节点定义与辅助函数为了构建测试用例我们需要先定义树节点并编写一个简单的建树函数这里为了方便使用静态创建的方式。#include iostream #include map #include queue #include vector // 二叉树节点定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 辅助函数根据数组创建二叉树层序创建-1表示空节点 // 注意此函数仅为方便测试非算法核心部分 TreeNode* createTree(const std::vectorint nodes) { if (nodes.empty() || nodes[0] -1) return nullptr; TreeNode* root new TreeNode(nodes[0]); std::queueTreeNode* q; q.push(root); int i 1; while (!q.empty() i nodes.size()) { TreeNode* curr q.front(); q.pop(); // 处理左孩子 if (i nodes.size() nodes[i] ! -1) { curr-left new TreeNode(nodes[i]); q.push(curr-left); } i; // 处理右孩子 if (i nodes.size() nodes[i] ! -1) { curr-right new TreeNode(nodes[i]); q.push(curr-right); } i; } return root; } // 辅助函数删除二叉树释放内存防止内存泄漏 void deleteTree(TreeNode* root) { if (root nullptr) return; deleteTree(root-left); deleteTree(root-right); delete root; }5.2 DFS递归版本完整实现// DFS递归版本计算垂直总和 void calculateVerticalSumDFS(TreeNode* node, int hd, std::mapint, int verticalSum) { if (node nullptr) { return; } // 累加当前节点值到对应HD的桶中 verticalSum[hd] node-val; // 递归处理左右子树HD相应增减 calculateVerticalSumDFS(node-left, hd - 1, verticalSum); calculateVerticalSumDFS(node-right, hd 1, verticalSum); } // 对外接口函数 std::mapint, int getVerticalSumDFS(TreeNode* root) { std::mapint, int verticalSum; calculateVerticalSumDFS(root, 0, verticalSum); return verticalSum; // 返回按HD排序的map }5.3 BFS迭代版本完整实现// BFS迭代版本计算垂直总和 std::mapint, int getVerticalSumBFS(TreeNode* root) { std::mapint, int verticalSum; if (root nullptr) return verticalSum; std::queuestd::pairTreeNode*, int q; // 队列存储节点指针, HD q.push({root, 0}); while (!q.empty()) { auto [currentNode, currentHd] q.front(); q.pop(); verticalSum[currentHd] currentNode-val; if (currentNode-left ! nullptr) { q.push({currentNode-left, currentHd - 1}); } if (currentNode-right ! nullptr) { q.push({currentNode-right, currentHd 1}); } } return verticalSum; }5.4 测试主函数与多种用例// 打印垂直总和结果 void printVerticalSum(const std::mapint, int sumMap) { std::cout Vertical Sums (HD - Sum): std::endl; for (const auto [hd, sum] : sumMap) { // C17结构化绑定遍历map std::cout HD hd : sum std::endl; } // 或者输出为数组格式 std::cout As array: [; bool first true; for (const auto [hd, sum] : sumMap) { if (!first) std::cout , ; std::cout sum; first false; } std::cout ] std::endl std::endl; } int main() { // 测试用例1标准二叉树 std::cout Test Case 1: Standard Tree std::endl; std::vectorint nodes1 {1, 2, 3, 4, 5, -1, 6}; // -1表示空节点 TreeNode* root1 createTree(nodes1); auto sumMapDFS1 getVerticalSumDFS(root1); auto sumMapBFS1 getVerticalSumBFS(root1); std::cout DFS Result: std::endl; printVerticalSum(sumMapDFS1); std::cout BFS Result: std::endl; printVerticalSum(sumMapBFS1); deleteTree(root1); // 测试用例2空树 std::cout Test Case 2: Empty Tree std::endl; TreeNode* root2 nullptr; auto sumMapDFS2 getVerticalSumDFS(root2); auto sumMapBFS2 getVerticalSumBFS(root2); std::cout DFS Result: std::endl; printVerticalSum(sumMapDFS2); // 应输出空 std::cout BFS Result: std::endl; printVerticalSum(sumMapBFS2); // 应输出空 // 测试用例3只有左子树的链状树 std::cout Test Case 3: Left-skewed Tree std::endl; std::vectorint nodes3 {1, 2, -1, 3, -1, -1, -1}; // 1 - 2 - 3 TreeNode* root3 createTree(nodes3); auto sumMapDFS3 getVerticalSumDFS(root3); std::cout DFS Result: std::endl; printVerticalSum(sumMapDFS3); // HD: -2:3, -1:2, 0:1 deleteTree(root3); // 测试用例4单节点树 std::cout Test Case 4: Single Node Tree std::endl; TreeNode* root4 new TreeNode(100); auto sumMapDFS4 getVerticalSumDFS(root4); std::cout DFS Result: std::endl; printVerticalSum(sumMapDFS4); // HD: 0:100 deleteTree(root4); return 0; }编译并运行上述代码需要支持C17的编译器如g 7以上或MSVC 2017以上你将看到四个测试用例的输出验证算法在不同树形结构下的正确性。6. 算法变体、边界处理与性能考量6.1 如果结果需要存入向量而非Map有时面试官或题目要求直接返回一个向量std::vectorint按HD从小到大的顺序存放垂直总和。由于我们使用的std::map本身已按键HD排序转换非常简单std::vectorint getVerticalSumAsVector(TreeNode* root) { std::mapint, int sumMap getVerticalSumDFS(root); // 或用BFS版本 std::vectorint result; // 将map中的值sum按顺序提取到vector for (const auto [hd, sum] : sumMap) { result.push_back(sum); } return result; }注意这里直接遍历map利用其有序性。如果使用unordered_map则需要先将键HD提取到一个向量中排序再按排序后的HD顺序从map中取值多了一步操作。6.2 处理大数求和与溢出问题节点值val通常是整数int。当树很大且同一垂直线上节点值累计可能超过int类型的范围时就会发生整数溢出。这是生产环境中必须考虑的问题。解决方案如果题目明确节点值范围或总和不会太大用int即可。如果存在溢出风险应将累加和的类型改为更宽的类型如long long或int64_t。修改std::mapint, int为std::mapint, long long即可。std::mapint, long long getVerticalSumLarge(TreeNode* root) { std::mapint, long long verticalSum; // ... DFS或BFS逻辑累加时使用long long // verticalSum[hd] static_castlong long(node-val); return verticalSum; }6.3 空间复杂度优化探讨我们算法的空间消耗主要在两方面递归调用栈或BFS队列和哈希表。递归栈/队列无法避免必须存储待访问节点。哈希表我们使用了std::map。有没有可能不用额外的哈希表一种思路是进行两次遍历第一次确定HD的最小值和最大值从而确定总和数组的大小第二次遍历将值累加到数组对应偏移的位置。伪代码如下// 第一次遍历找最小和最大HD void findMinMaxHD(TreeNode* node, int hd, int minHd, int maxHd) { if (!node) return; minHd std::min(minHd, hd); maxHd std::max(maxHd, hd); findMinMaxHD(node-left, hd-1, minHd, maxHd); findMinMaxHD(node-right, hd1, minHd, maxHd); } // 第二次遍历累加到数组 void accumulateSum(TreeNode* node, int hd, int offset, std::vectorint result) { if (!node) return; result[hd offset] node-val; // offset用于将负HD映射到数组索引 accumulateSum(node-left, hd-1, offset, result); accumulateSum(node-right, hd1, offset, result); } std::vectorint getVerticalSumTwoPass(TreeNode* root) { if (!root) return {}; int minHd 0, maxHd 0; findMinMaxHD(root, 0, minHd, maxHd); int width maxHd - minHd 1; int offset -minHd; // 使最小HD对应索引0 std::vectorint result(width, 0); accumulateSum(root, 0, offset, result); return result; }优化对比两遍遍历法空间复杂度为O(W)其中W是HD的宽度maxHd - minHd 1通常小于或等于节点数N。它避免了哈希表的开销红黑树的节点或哈希表的桶。哈希表单遍法空间复杂度为O(N)但代码更简洁且当树比较稀疏W接近N时两者空间差别不大。如何选择在大多数情况下哈希表单遍法的简洁性和可读性优势更大除非内存极度受限且已知树非常“宽而浅”。面试中先给出哈希表方案再提及两遍遍历作为优化思路会显得思考更全面。7. 常见问题排查与调试技巧7.1 结果不正确检查HD计算与累加位置这是最常见的错误。请对照以下清单检查根节点HD初始值必须从0开始。左右子树HD传递左子树hd - 1右子树hd 1。符号千万别搞反。累加操作的位置必须在访问节点将其值加入map之后再递归调用左右子树。如果放在递归调用之后逻辑上也没错但不符合前序遍历的习惯。map的引用传递在DFS递归版本中verticalSum必须通过引用传递否则每个递归帧都会操作map的副本结果无法汇总。空节点判断递归函数开头或访问子节点前判断nullptr避免空指针解引用。7.2 内存泄漏别忘了释放二叉树我们的测试代码中手动new了节点因此必须在程序结束前delete。使用deleteTree这样的后序遍历递归删除是标准做法。在实际项目或在线判题系统中通常由系统管理内存但自己写测试代码时务必注意养成“谁申请谁释放”的习惯。7.3 使用调试器如GDB/VS Debugger观察递归过程对于递归算法单步调试是理解其运行过程的神器。你可以在递归函数入口设置断点。观察每次调用时node-val和hd的值。观察verticalSummap 内容的变化。查看调用栈Call Stack理解递归的深入与返回。7.4 可视化工具辅助理解对于树相关问题画图是最直观的。可以手动画小树标注每个节点的HD然后模拟算法流程。也可以使用一些在线的二叉树可视化工具如 visualgo.net 上的二叉树模块虽然它们不一定直接支持HD标注但帮你理清树结构本身就有很大帮助。8. 从垂直总和到相关算法拓展理解垂直总和算法后你可以轻松解决一系列变体问题因为它们核心的“HD映射”思想是相通的。8.1 变体一求二叉树的垂直视图问题返回二叉树每一列从上到下所有节点中第一个出现的节点值通常是该列最顶部的节点。思路依然用DFS/BFS和map但map的值不再是一个累加和而是一个节点值。在遍历时如果当前HD在map中不存在即该列还未记录节点则存入当前节点值。注意如果使用BFS层序遍历天然保证了从上到下的顺序第一次遇到某个HD时记录的节点就是该列最顶部的节点。如果使用DFS则需要记录节点的行号深度并选择行号更小更浅的节点实现稍复杂。8.2 变体二求二叉树的最宽垂直层问题定义垂直层的宽度为该层最左节点和最右节点的HD之差加1。求整个二叉树中最宽的垂直层宽度。思路在遍历过程中记录遇到的最小HD和最大HD。最终宽度就是maxHd - minHd 1。这甚至不需要map只需要两个变量在遍历过程中更新极值即可。8.3 变体三带深度信息的垂直遍历问题返回一个二维数组第一维是HD第二维是该HD下按深度行号排序的节点值列表。思路此时map的值需要是一个更复杂的数据结构例如mapint, vectorpairint, int其中内层pair存储深度节点值。遍历时将深度节点值插入对应HD的vector中。遍历完成后对每个HD对应的vector按深度排序再提取出节点值列表。通过解决垂直总和这个具体问题我们掌握了“为树节点赋予坐标并进行聚合”的范式。这个范式可以灵活运用于许多其他树形结构的问题中例如在更复杂的场景中你可能需要同时记录行号和列号HD来实现二维的拓扑排序或视图生成。