2011 年的 408 真题第 4 题是一道让很多人“好像会做又说不清为什么”的题目一棵完全二叉树有 768 个结点问叶子结点有多少个。有些同学在考场上直接凭印象写“结点数除以 2”得到 384也有人犹豫半天最后选了 383 或 385。这两种情况本质上的差别不在于“会不会除法”而在于对完全二叉树性质的掌握是否到能推导的程度。这道题真正想考察的不是“你会不会背公式”而是“你能不能从定义出发在 3 分钟之内把公式推出来”。一旦推出来你不仅会做 768 这个数字还能应对各种变形题。本文就从这道真题出发把完全二叉树的叶子结点计算讲透给出三种推导思路、完整的代码验证以及复习时最值得注意的坑。1. 题目定位2011 年 408 第 4 题在考什么先明确题目信息。题干的关键词是“完全二叉树”“768 个结点”“叶子结点数”。二叉树中度为 0 的结点叫叶子结点度为 1 的结点只有一个孩子度为 2 的结点有两个孩子。这个定义是后续所有推导的基础。完全二叉树是二叉树的一种特殊形态除最后一层外其他各层都被填满且最后一层的结点全部靠左连续排列。这里要建立一个判断408 统考中这类性质题的真正考点不是“套公式”而是“理解完全二叉树为什么能让公式简化”。如果你只记住叶子结点数等于结点数的一半遇到本题可能勉强能答对但后续只要题目换一个角度比如“第 6 层有 8 个叶结点求最多结点数”你就会无从下手。因此下面的篇幅不再只讲“答案是 384”而是把从题目到答案的完整逻辑链展开让你在考场上不需要背任何现成结论。2. 完全二叉树的核心性质度为 1 的结点为什么只能是 0 或 1要计算叶子结点数最常用的工具是二叉树中三类结点数量之间的关系。设叶子结点数为 n0度为 1 的结点数为 n1度为 2 的结点数为 n2。对于任何一棵二叉树都有两个基本等式总边数 结点数 - 1 n0 n1 n2 - 1总边数也可以表示为 n1 2n2两边联立得到n0 n2 1这个结论对任意二叉树都成立它是一个通用性质不限于完全二叉树。比如一棵只有根结点的树n2 0n0 1显然成立。把这个结论代入总结点数公式n n0 n1 n2 n0 n1 (n0 - 1) 2n0 n1 - 1所以n0 (n 1 - n1) / 2到这里问题就集中在 n1 的取值上。对于完全二叉树n1 要么是 0要么是 1不可能超过 1。原因是完全二叉树按层序编号后结点从左到右连续排列。假设某个结点只有一个孩子那么它一定是最后一个有孩子的结点。因为如果它后面还有其他结点有孩子这些孩子的编号会排在这个结点孩子的右侧而完全二叉树要求连续这就矛盾了。同理完全二叉树不允许一个结点只有右孩子而没有左孩子因为这样会造成编号不连续。更直观地说一个完全二叉树最多只有一个“单分支”结点。当总结点数为偶数时n1 1当总结点数为奇数时n1 0。用几个小例子就能验证n 3 时根结点有两个孩子叶子是下面两个n1 0n 4 时根结点有两个孩子左孩子还有左孩子最左下结点有一个左孩子n1 1所以n0 (n 1 - n1) / 2只要确定 n1 是 0 还是 1 即可。对 768 这个偶数n1 1代入后n0 (768 1 - 1) / 2 384这个方法建议作为考场首选因为它不依赖背诵“除以 2”还是“除以 2 加 1”而是从 n1 的取值出发自己推导。即使忘记结论只要记得总度数关系和完全二叉树单分支结点的特性就能很快算出来。3. 结点编号法从“叶子判定条件”直接数出来如果觉得上面的推导稍显抽象可以换一个角度完全二叉树按层序编号之后每个结点的编号自带丰富信息。假设根结点编号为 1左孩子编号为 2i右孩子编号为 2i 1。那么一个结点 i 是否有左孩子取决于 2i 是否超过总结点数 n。如果 2i n说明编号 i 的结点没有左孩子。对于完全二叉树一个结点不可能只有右孩子而没有左孩子因此 2i n 等价于该结点是叶子。于是叶子结点数就是在 1 到 n 之间满足 2i n 的 i 的个数。只看条件 2i n可以推出 i n / 2也就是 i ⌊n/2⌋ 1。当 n 768 时⌊n / 2⌋ 384编号 385 到 768 的结点都满足 2i 768这一共有 768 - 385 1 384 个所以叶子结点数是 384。这个方法的优势在于它直接对应完全二叉树的数组存储结构。在堆排序、优先队列这些考试高频考点中数组下标从 1 开始存放完全二叉树时叶子结点恰好就是下标从 ⌊n/2⌋ 1 到 n 的区间。理解了编号法再去做堆的向下调整、建堆的 O(n) 复杂度分析会有更清晰的感觉。对小规模例子验证一下n 5 的完全二叉树编号分别是 1 到 5。满足 2i 5 的 i 有 3、4、5共 3 个叶子。n0 (5 1) / 2 3两者一致。此法和第一种方法互为印证。考场上用哪种都可以但建议两种都掌握。因为遇到“已知某个编号求它的父结点、左右孩子”这类题时编号法几乎是标准解法。4. 分层计算法直观但容易在层号上翻车第三种思路是从“一层一层数”的角度出发。这个方法足够直观适合用来检查答案但新手很容易因为层号从 0 还是从 1 开始算而丢分。按照 408 统考的默认约定根结点所在层为第 1 层。一棵有 n 个结点的完全二叉树高度 h 满足2^(h-1) n 2^h计算层数时可以先找到最大的 k使得 2^k n然后用 h k 1 表示层数。例如 n 7682^9 5122^10 1024512 768 1024因此高度为 10完整的前 9 层共有 2^9 - 1 511 个结点最后一层就有 768 - 511 257 个结点。这些最后一层结点全部是叶子。接下来看倒数第二层也就是第 9 层。这一层原本满的情况下应该有 2^8 256 个结点。现在最后一层有 257 个结点它们在完全二叉树中靠左连续排列所以这些结点对应的父结点是第 9 层的前若干个结点。257 个孩子最少需要 ⌈257 / 2⌉ 129 个父结点。于是第 9 层有孩子的结点数是 129剩下的 256 - 129 127 个结点是叶子。叶子总数 最后一层 257 倒数第二层 127 384。这里特别要提醒的是很多人会把“前 9 层共有 511 个结点”和“第 9 层有 256 个结点”搞混。511 是前 9 层总和256 是第 9 层单独的数量。计算倒数第二层叶子数时用的必须是 256不是 511。分层法能帮助你直观看到“叶子分布在最后两层”这一事实。在更复杂的变形题比如“已知第 6 层有若干叶结点求整棵树最多有多少结点”时分层法反而是最可靠的方法。后面第 7 小节的变式题就会用到它。5. 三种方法对比考场上应该选哪一种把三种方法放在一起看它们其实是从不同侧面描述同一个事实。解法核心依据计算速度稳定性度数关系法n0 n2 1n1 取 0 或 1最快高结点编号法编号 i 的叶子条件 2i n快高分层计算法叶子集中在最后两层中等较低层号易错如果你只追求考场上快速得出正确答案推荐第一种。因为它只有三步奇数偶数判断、n1 取值、代入公式。768 是偶数n1 1结果就是 n / 2 384。但如果题目出现“已知叶子结点数反推总结点数”这类问法单纯用度数关系法可能会遇到多个候选值。此时编号法和分层法能帮你筛掉不满足完全二叉树连续编号条件的答案。所以更合理的策略是核心结论用度数关系法秒算遇到不确定的情况再用分层法画图验证。6. 代码验证用程序把 768 这个结论跑出来光推导不验证总觉得不够踏实。下面用三段 Python 代码分别实现三种解法。程序不是考试要求但能帮你建立直觉也可以用来验证任意结点数 n 的情况非常适合在复习时自查。6.1 公式法根据 n1 取值直接计算def leaf_count_by_formula(n): # 完全二叉树中 n1 只能为 0 或 1 # 当 n 为偶数时n1 1 # 当 n 为奇数时n1 0 # 叶子数 n0 (n 1 - n1) // 2 if n % 2 0: n1 1 else: n1 0 return (n 1 - n1) // 2 print(leaf_count_by_formula(768))这个实现的思路与第 2 小节的推导完全一致。n 768 是偶数n1 1输出为 384。6.2 编号法统计满足 2i n 的结点def leaf_count_by_index(n): count 0 for i in range(1, n 1): if 2 * i n: count 1 return count print(leaf_count_by_index(768))这段代码直接模拟层序编号后的叶子判定条件。对每个编号 i判断其左孩子编号 2i 是否超过总编号 n。超过则说明该结点没有左孩子在完全二叉树中也必然没有右孩子因此是叶子。输出同样是 384。6.3 建树验证构造真正的完全二叉树再数叶子如果不想只靠公式可以真正构造一棵包含 768 个结点的完全二叉树然后遍历统计叶子数。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_complete_tree(n): if n 0: return None nodes [TreeNode(i) for i in range(1, n 1)] for i in range(1, n 1): if 2 * i n: nodes[i - 1].left nodes[2 * i - 1] if 2 * i 1 n: nodes[i - 1].right nodes[2 * i] return nodes[0] def count_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) count_leaves(root.right) root build_complete_tree(768) print(count_leaves(root))这段代码的关键是 build_complete_tree 中的下标映射。数组中下标从 0 开始但完全二叉树编号从 1 开始所以编号 i 的结点存放在 nodes[i - 1] 中其左孩子编号 2i 对应 nodes[2 * i - 1]右孩子编号 2i 1 对应 nodes[2 * i]。递归统计叶子时只要左右孩子都为空就计入叶子。运行三段代码后输出应一致384 384 384如果三个方法输出不一致说明你的程序或推导过程至少有一步出了问题。这种“多方案互相验证”的思路在复习时比单纯做题更有价值。7. 真题变式从“给结点数求叶子”到“给叶子数求结点数”408 真题很少把同一个考点原封不动地考第二遍。更常见的是变换条件考察你能否把原理迁移过去。这里举一个典型的变式已知一棵完全二叉树的第 6 层有 8 个叶结点求这棵完全二叉树最多有多少个结点。首先要明确题目没有说明树只有 6 层所以树的高度可能大于 6。要使得结点总数最多树的高度要尽可能大并且各层结点数尽可能满。设根为第 1 层则第 6 层最多有 2^5 32 个结点。题目说这一层有 8 个叶结点意味着第 6 层其余 24 个结点不是叶结点它们可以有孩子。如果想让整棵树结点最多就让第 6 层这 24 个非叶结点都生两个孩子也就是第 7 层最多有 24 × 2 48 个结点。此时前 6 层是一个满二叉树结点数为 2^6 - 1 63第 7 层有 48 个结点总数就是63 48 111注意这里有一个隐含前提第 6 层的 8 个叶结点应该尽可能靠右。因为完全二叉树要求最后一层结点靠左连续为了让第 7 层结点数最多第 6 层前面的结点必须尽量都有两个孩子。如果 8 个叶结点出现在最左侧就会导致第 7 层可排列的位置变少结点总数也会变小。所以这类型变式的核心是两条定位层号判断哪些层完全填满根据“叶子靠右排”“非叶结点尽量有孩子”来确定下一层数量。一旦你完全理解了第 4 小节的分层法这类题只需要再多想一步题目问的是最大值还是最小值。最大值让非叶结点全部有孩子最小值让非叶结点尽量没有孩子。遇到这种变形时建议先画一棵只有 10 个左右结点的小树把“层号”“叶结点位置”“父结点数量”三个要素标出来再套到具体数字上。画图是考场外最好的练习方式它能帮你修正很多不靠谱的直觉。8. 从 768 这道题看 408 的复习方法每年准备 408 的同学都会在数据结构上投入大量时间但效果差异很大。差异往往不在刷题量而在做题方式。就拿二叉树性质这部分来说常见的学习路径有两种。一种是把各种结论整理成一张表开始背二叉树叶子数等于 n2 1完全二叉树叶子数是 ⌈n/2⌉高度是 ⌊log2 n⌋ 1结点编号满足双亲为 ⌊i/2⌋……背完之后做对了几道题感觉很顺利。一旦题目条件改一改比如“某层有 8 个叶结点”或“已知前序中序还原树”就手忙脚乱。另一种是从定义出发把结论推一遍。你会发现大量公式其实是同一条逻辑链的产物。n0 n2 1 来自边的计数完全二叉树 n1 只能是 0 或 1 来自层序编号的连续性层数公式来自满二叉树结点数量的等比数列求和。推清楚这些做题不需要背表。具体到复习步骤可以这样做第一步把二叉树的度数定义、完全二叉树定义写在纸上不看教材。第二步自己推一遍叶子数与总结点数的关系推不动再翻书。第三步用 n 1 到 7 的小规模完全二叉树验证公式。第四步把公式改写成代码用程序批量验证 n 1 到 1000 的情况。第四步听起来麻烦其实写一个循环就足够。下面这段代码可以一次性验证公式和编号法从 n 1 到 n 1000 的一致性def verify(n): # 公式法 if n % 2 0: count1 n // 2 else: count1 (n 1) // 2 # 编号法 count2 sum(1 for i in range(1, n 1) if 2 * i n) return count1 count2 all_ok all(verify(n) for n in range(1, 1001)) print(1 到 1000 全部一致, all_ok)这个验证过程能帮你发现比如当 n 999 时叶子数是 500而不是 449。通过代码把边界情况全部过一遍比死记“奇数和偶数不一样”要牢靠得多。对于时间紧张的同学我的建议是第一轮复习时不要跳过推导第二轮再开始刷真题遇到遗忘的公式就快速重新推一遍。408 的题目风格不是考你背诵能力而是考你在有限时间内把知识点组合起来解决问题的能力。这个能力只能靠“推导训练”获得。9. 常见错误与考场陷阱虽然这道题本身计算量不大但每年都有考生在细节上出错。下面整理几个高频错误你可以对照自查。错误现象原因分析正确做法768 除以 2 等于 384直接写但说不清为什么只背结论不理解 n1 取值变化掌握度数关系推导算出 383 或 385把 n1 的取值判断反了记住偶数 n 时 n1 1分层法算出 257 或 255只数了最后一层叶子漏掉倒数第二层叶子叶子分布在最后两层层数写成 9 或 11层号从 0 开始计数或对高度公式使用不当明确根为第 1 层把完全二叉树当成满二叉树没注意最后一层可以不满复习定义画图对比只知道公式不会反推只会正向套用不理解结构限制练习变式题特别想提醒的是“完全二叉树是否等于满二叉树”这个问题。很多初学者看到“完全”两个字就默认每层都是满的。实际上满二叉树是完全二叉树的特殊情况完全二叉树允许最后一层不满但必须靠左排列。如果题目明确说是“满二叉树”那 768 个结点由于 768 不是 2^k - 1 的形式根本不可能成立所以题干中的关键字一定是“完全二叉树”千万不要看漏。考场上的时间分配也很重要。这类性质题如果在 2 分钟内没有头绪建议先跳过不要卡住节奏。等做完后面的大题再回头用第二种方法重新算。因为二叉树性质题通常只要画一棵小树就能找到灵感时间压力解除后复杂度会明显下降。10. 总结与后续学习方向这道 768 个结点的完全二叉树求叶子数看似只有数字和公式实际上把完全二叉树最核心的几条性质都串了起来。度数关系告诉你 n0 n2 1完全二叉树结构告诉你 n1 只能取 0 或 1层序编号告诉你叶子结点从 ⌊n/2⌋ 1 开始。三个角度指向同一个答案384。建议收藏本文复习的时候把三种方法分别推一遍再用代码跑一遍。推完这道题你可以继续挑战这些方向完全二叉树的数组存储与堆排序的关系由完全二叉树的层序序列还原树结构已知叶子结点所在层数求总结点数的最大最小值二叉树的遍历序列到唯一二叉树的还原平衡二叉树、哈夫曼树与完全二叉树的性质对比。这些考点看起来分散底层还是“树”这一章的基本功。把一棵树的度、结点数、深度、路径这几个概念吃透后面学图、学排序都会轻松很多。下次再看到类似的题目别急着套结论先问自己一句这个结论我能现场推出来吗能推出来才算真正掌握。