1. 从零拆解二叉树与堆：为什么ACM选手绕不开这两个结构
二叉树和堆，几乎是所有算法竞赛入门阶段最先撞上的两堵墙。很多人第一次打开题目，看到“给定一棵完全二叉树，求第k小的节点值”或者“维护一个动态集合，支持插入和查询最小值”，脑子里第一反应是用数组排序，结果提交上去不是超时就是内存爆掉。问题出在哪？出在没有意识到这两个结构本质上解决的是同一类问题：在数据不断变化的情况下，如何快速找到某个特定位置的元素。
我接触过不少刚入门的同学，他们刷题时习惯按标签走，看到“二叉树”就去找递归模板，看到“堆”就去调库函数。这种打法在简单题上能混过去，一旦遇到需要手写调整的题目就原形毕露。比如“数据流的中位数”这道经典题，本质上是维护两个堆的平衡，但如果你对堆的底层数组表示和上浮下沉操作没有肌肉记忆，考场上现推是来不及的。
这篇文章面向的是正在准备算法竞赛、或者想系统补一下基础数据结构的读者。不管你是刚学完C语言语法的新手，还是已经刷了几百道题但总觉得基础不牢的老手，下面这些内容都能帮你把二叉树和堆的底层逻辑重新捋一遍。我会从实际编码角度出发，讲清楚每个操作背后的数组下标关系、递归与迭代的取舍、以及那些模板代码里不会告诉你的边界处理技巧。
2. 二叉树的核心逻辑与手写实现要点
2.1 二叉树的存储方式：指针还是数组
二叉树的存储方式直接决定了你后面所有操作的代码形态。用指针节点（struct Node { int val; Node *left, *right; }）的好处是结构直观，动态增删方便，适合树形不确定、需要频繁插入删除的场景。但缺点也很明显：每次访问子节点都要解引用，缓存不友好，而且在竞赛中频繁new节点容易导致内存碎片和超时。
用数组存储则分为两种情况。一种是静态数组模拟指针，开一个足够大的node池，用整数下标代替指针，这样既保留了指针的灵活性，又避免了动态内存分配的开销。另一种是完全二叉树的数组表示，根节点下标为1，左孩子为2i，右孩子为2i+1，父节点为i/2。这种表示法在堆和线段树中极为常见，因为它天然支持随机访问，而且不需要存储额外的指针信息。
我个人的经验是：如果题目明确说了是完全二叉树，或者你判断树的结构不会太深，优先用数组。如果是一般的二叉树且需要动态构建，用静态数组模拟指针。真正用指针加new的场合，反而是在一些需要持久化或者共享子树的场景中。
2.2 遍历方式的本质区别与选择策略
前序、中序、后序、层序，这四种遍历方式的名字大家都背得出来，但什么时候用哪种，很多人是凭感觉。前序遍历的本质是“先处理当前节点，再处理子树”，适合需要自顶向下传递信息的场景，比如求根到叶子的路径和。中序遍历在二叉搜索树中会输出有序序列，这是它最核心的价值。后序遍历则是“先处理子树，再处理当前节点”，适合需要自底向上汇总信息的场景，比如求树的高度、判断平衡二叉树。
层序遍历用队列实现，适合处理与“层”相关的问题，比如求树的宽度、按层打印、找最底层最左边的节点。这里有一个容易踩的坑：层序遍历时，队列中同时存在不同层的节点，如果你需要区分每一层，必须在进入循环时记录当前队列的大小，然后只处理这么多节点。这个技巧在“二叉树的右视图”和“二叉树的最大宽度”中都会用到。
递归实现遍历时，要注意递归深度。对于一棵退化成链的二叉树，递归深度可能达到节点数量，如果节点数在10^5级别，系统栈可能会溢出。这时候要么改用迭代加显式栈，要么在递归函数开头判断深度并手动扩大栈空间。竞赛中更稳妥的做法是直接写迭代版本。
2.3 二叉搜索树的增删查改与边界处理
二叉搜索树（BST）的核心性质是：对于任意节点，其左子树所有节点的值小于它，右子树所有节点的值大于它。这个性质使得查找、插入、删除的平均时间复杂度都是O(log n)。但要注意，这是平均情况，如果插入序列本身有序，BST会退化成链表，时间复杂度变成O(n)。这就是为什么后面出现了平衡树，但在ACM入门阶段，手写BST仍然是必须掌握的技能。
插入操作比较简单，递归找到空位置放进去就行。查找也是类似。真正麻烦的是删除操作，分三种情况：删除叶子节点直接删；删除只有一个孩子的节点，用孩子替代；删除有两个孩子的节点，需要找到右子树的最小值（或左子树的最大值）来替代当前节点，然后递归删除那个最小值节点。
这里有一个细节：找右子树最小值时，要一直往左走直到没有左孩子。替代之后，不要忘记把替代节点的左右孩子指针接好。很多人在这一步出错，导致树结构断裂。我建议在写删除操作时，先画出三种情况的示意图，确认指针的指向关系后再写代码。
2.4 递归与迭代的取舍：以遍历和求高度为例
递归写起来简洁，但有两个问题：一是栈溢出风险，二是函数调用开销。在ACM竞赛中，如果递归深度可能很大，或者对常数时间敏感，就需要改成迭代。以中序遍历为例，迭代版本需要显式维护一个栈，先把当前节点及其所有左孩子入栈，然后弹出栈顶访问，再转向右孩子。这个过程可以用一个while循环加内层while循环实现。
求树的高度也可以用迭代加队列做层序遍历，每处理完一层高度加一。但更常见的做法是后序递归，因为代码短。如果题目数据范围不大，递归完全够用。但如果节点数达到10^6，就必须考虑迭代了。
我个人的习惯是：先写递归版本，确认逻辑正确后，如果时间或空间紧张，再改成迭代。不要一上来就追求迭代，那样容易在指针操作上浪费大量调试时间。
3. 堆的底层原理与手写调整技巧
3.1 堆的数组表示与下标计算
堆是一棵完全二叉树，用数组存储时，下标从1开始（也可以从0开始，但1开始的下标计算更简洁）。对于下标为i的节点，父节点下标为i/2（整数除法），左孩子为2i，右孩子为2i+1。这个关系是堆所有操作的基础，必须烂熟于心。
为什么从1开始？因为如果从0开始，父节点下标是(i-1)/2，左孩子是2i+1，右孩子是2i+2，公式稍微复杂一点，而且判断边界时容易出错。竞赛中为了减少思维负担，通常开一个大小为n+1的数组，下标0不用。
堆分为大根堆和小根堆。大根堆的每个节点值都大于等于其孩子，小根堆则相反。C++的priority_queue默认是大根堆，如果要小根堆，可以插入负数或者自定义比较器。但在需要手写堆的题目中，你必须自己实现上浮和下沉。
3.2 上浮与下沉：堆的两个核心操作
上浮（shift up）用于插入新元素。把新元素放到数组末尾，然后不断与父节点比较，如果比父节点更符合堆性质（大根堆中比父节点大），就交换，直到满足堆性质或到达根节点。时间复杂度O(log n)。
下沉（shift down）用于删除堆顶。把堆顶元素与最后一个元素交换，然后删除最后一个元素，再对新的堆顶执行下沉：与左右孩子中更符合堆性质的那个比较，如果孩子更符合，就交换，直到满足堆性质或到达叶子。时间复杂度O(log n)。
这两个操作的代码必须能默写。我见过很多人在面试或比赛中卡在下沉时的边界判断上，比如忘记判断右孩子是否存在，或者比较时用了错误的方向。建议在写的时候，先明确是大根堆还是小根堆，然后统一比较逻辑。
3.3 建堆的两种方式与复杂度分析
建堆有两种方式：一种是逐个插入，每次插入执行上浮，总时间复杂度O(n log n)。另一种是从最后一个非叶子节点开始，依次对每个节点执行下沉，总时间复杂度O(n)。很多人不理解为什么第二种是O(n)，这里简单解释一下：下沉操作的时间与节点所在的高度成正比，而高度越低的节点越多，高度越高的节点越少。对所有节点的高度求和，可以得到一个收敛的级数，最终是O(n)。
在竞赛中，如果题目要求建堆，优先用第二种方式，因为常数更小。具体做法是：从n/2开始，倒着遍历到1，对每个节点执行下沉。注意n/2是最后一个非叶子节点的下标，因为叶子节点本身已经满足堆性质，不需要调整。
3.4 堆排序的完整流程与稳定性讨论
堆排序分为两步：建堆和排序。建堆用上述O(n)的方式。排序时，每次把堆顶与当前最后一个元素交换，然后堆的大小减一，再对堆顶执行下沉。重复n-1次，数组就有序了。如果是大根堆，排序结果是升序；小根堆则是降序。
堆排序是不稳定的，因为交换操作可能改变相同元素的相对顺序。但在ACM中，稳定性通常不是考察重点，除非题目明确要求。堆排序的优势在于原地排序，空间复杂度O(1)，而且最坏时间复杂度也是O(n log n)。缺点是对缓存不友好，因为访问模式是跳跃的。
4. 二叉树与堆的经典题型实战拆解
4.1 二叉树的深度与平衡判断
求二叉树的最大深度是入门题，递归一行搞定：maxDepth(root) = max(maxDepth(left), maxDepth(right)) + 1。但如果是判断平衡二叉树，就不能只求深度了，因为需要同时判断左右子树的高度差是否超过1。这时候可以用后序遍历，在递归过程中返回高度，如果发现不平衡就返回-1作为标记。
这里有一个常见的错误：在判断平衡时，对每个节点都调用一次求深度的函数，导致时间复杂度变成O(n^2)。正确的做法是在一次后序遍历中同时完成高度计算和平衡判断。这个优化思路在“二叉树的直径”等题目中也会用到。
4.2 二叉搜索树的验证与修复
验证一棵树是否是BST，不能简单地判断每个节点与其左右孩子的大小关系，因为BST要求的是整个左子树都小于根，整个右子树都大于根。正确做法是传递上下界，递归判断每个节点是否在合法范围内。或者用中序遍历，检查是否严格递增。
修复BST的题目通常是有两个节点被错误交换了。可以用中序遍历找到这两个节点，然后交换它们的值。这里要注意，中序遍历时如果发现前一个节点的值大于当前节点，说明找到了一个错误点。但可能有两个错误点，需要记录第一次和最后一次。
4.3 数据流中的第K大元素：堆的经典应用
维护一个大小为K的小根堆，堆顶就是第K大元素。每次插入新元素时，如果堆大小小于K，直接插入；否则如果新元素大于堆顶，弹出堆顶并插入新元素。这样堆中始终保存着当前最大的K个元素，堆顶就是第K大。
这个思路可以扩展到“数据流的中位数”：维护一个大根堆和一个小根堆，大根堆保存较小的一半，小根堆保存较大的一半。插入时根据大小关系选择堆，然后调整两个堆的大小差不超过1。中位数就是两个堆顶的平均值或其中一个堆顶。
4.4 合并K个有序链表：堆的另一种用法
合并K个有序链表，可以用一个大小为K的小根堆，初始时把每个链表的头节点放入堆中。每次弹出堆顶节点，接到结果链表后面，然后如果该节点有下一个节点，就把下一个节点放入堆中。重复直到堆为空。
这个题目的时间复杂度是O(N log K)，其中N是所有节点的总数。如果用两两合并的方式，时间复杂度是O(N K)，当K较大时效率明显下降。堆的解法在面试和竞赛中都是标准答案。
5. 常见问题与排查技巧实录
5.1 二叉树递归中的空指针与边界
递归函数开头一定要判断root是否为空，否则会段错误。这个看起来简单，但在复杂的递归逻辑中容易忘记。比如在“路径总和”题目中，如果当前节点为空，应该返回false，而不是继续访问左右孩子。
另一个常见问题是叶子节点的判断。叶子节点是左右孩子都为空的节点，而不是只有一个孩子为空。在“求根到叶子节点数字之和”中，如果误把只有一个孩子的节点当成叶子，结果就会出错。
5.2 堆操作中的下标越界与比较错误
下沉操作时，需要先判断左孩子是否存在（2i <= size），再判断右孩子是否存在（2i+1 <= size）。如果只判断了左孩子，访问右孩子时可能越界。另外，在比较左右孩子时，要选择更符合堆性质的那个。大根堆中选较大的孩子，小根堆中选较小的孩子。
上浮操作时，循环条件是i > 1，因为根节点没有父节点。如果写成i >= 1，当i=1时计算i/2得到0，访问heap[0]可能越界或得到错误值。
5.3 建堆时从哪个节点开始下沉
从最后一个非叶子节点开始，即n/2。如果从n开始，叶子节点下沉没有意义，浪费操作。如果从n/2+1开始，会漏掉一些非叶子节点。这个细节在手动建堆时容易搞错，建议每次写的时候都画一个简单的例子验证。
5.4 堆排序中的大小根堆选择
如果要用堆排序得到升序，必须用大根堆。因为每次把堆顶（最大值）交换到数组末尾，然后缩小堆的范围，这样最大值就固定在了最后。如果用小根堆，得到的是降序。这个逻辑不要记反。
5.5 常见问题速查表
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| 递归段错误 | 未判断空节点 | 在函数开头加if (!root) return; |
| 堆操作结果错误 | 下标计算错误 | 检查2i和2i+1是否越界 |
| 建堆后不是堆 | 下沉方向反了 | 确认大根堆选较大孩子 |
| BST验证失败 | 只比较了父子 | 改用上下界或中序遍历 |
| 堆排序结果降序 | 用了小根堆 | 改成大根堆 |
| 层序遍历分层错误 | 未记录当前层大小 | 在循环内先取队列size |
6. 手写堆与STL优先队列的取舍经验
C++的priority_queue用起来很方便，但它的局限性也很明显：不支持删除任意元素，不支持修改元素值，不支持合并两个堆。在需要这些操作的题目中，必须手写堆。比如“滑动窗口最大值”如果用优先队列，需要延迟删除，代码会变得复杂；而手写单调队列反而更简单。
手写堆的另一个好处是可控性强。你可以自定义比较函数，可以同时维护多个堆，可以在堆中存储结构体并按照某个字段排序。在ACM竞赛中，我建议至少能手写小根堆和大根堆的模板，这样遇到变种题目时不会慌。
STL优先队列的底层是vector加堆算法，默认是大根堆。如果要小根堆，可以写priority_queue<int, vector , greater >。对于自定义类型，需要重载operator<或者提供比较器。注意比较器的语义：priority_queue中的比较器返回true表示第一个参数优先级低于第二个参数，所以大根堆用less，小根堆用greater。
7. 从二叉树到堆：结构思维的迁移与扩展
二叉树和堆的关系，本质上是一般与特殊的关系。堆是一棵完全二叉树，并且满足偏序性质。理解了二叉树的各种遍历和递归思维，再学堆就会觉得顺理成章。反过来，堆的数组表示和上浮下沉操作，也可以迁移到其他完全二叉树结构上，比如线段树和树状数组。
线段树的每个节点维护一个区间的信息，它的数组表示和堆非常相似，也是根节点下标为1，左右孩子为2i和2i+1。树状数组虽然结构不同，但它的下标操作（i += i & -i）也和二进制表示有关。这些结构在高级算法中经常组合出现，比如“堆优化的Dijkstra”用优先队列，“线段树维护区间最值”用数组存储。
我个人的学习路径是：先手写二叉树的各种遍历和操作，再手写堆的插入删除建堆，然后刷一批经典题目巩固，最后看线段树和树状数组的代码时，会发现很多相似之处。这个顺序不要颠倒，否则容易在复杂结构面前失去方向。
8. 训练方法与刷题路线建议
如果你现在处于入门阶段，建议按以下顺序刷题：先做二叉树的遍历（前中后序、层序），再做二叉搜索树的验证、插入、删除，然后做堆的插入删除和堆排序，最后做综合题如数据流中位数、合并K个有序链表。每个类型做5到10道，确保能独立写出代码。
刷题时不要只看题解，要自己先想。如果10分钟没思路，可以看题解，但看完后要关掉题解自己写一遍。写完后对比题解的代码，看看自己的实现有没有可以优化的地方。比如递归能不能改成迭代，空间能不能压缩，边界处理能不能更简洁。
另外，建议准备一个模板本，把二叉树遍历、堆的上浮下沉、建堆、堆排序这些核心代码默写几遍，直到能不看任何资料写出来。竞赛中时间紧张，模板的熟练度直接决定了你能否快速AC。
最后分享一个我自己的习惯：每次遇到二叉树或堆的题目，先在纸上画出结构图，标出关键节点的下标或指针关系，然后再写代码。这个习惯帮我避免了很多下标越界和指针错误。尤其是堆的题目，画图能直观地看到上浮下沉的路径，比在脑子里模拟要可靠得多。
