企业官网建设流程全解析

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 = 0，n0 = 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 = 0
• n = 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 = 768：

• 2^9 = 512
• 2^10 = 1024
• 512 <= 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. 三种方法对比：考场上应该选哪一种

把三种方法放在一起看，它们其实是从不同侧面描述同一个事实。

如果你只追求考场上快速得出正确答案，推荐第一种。因为它只有三步：奇数偶数判断、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 个结点由于 768 不是 2^k - 1 的形式，根本不可能成立，所以题干中的关键字一定是“完全二叉树”，千万不要看漏。

考场上的时间分配也很重要。这类性质题如果在 2 分钟内没有头绪，建议先跳过，不要卡住节奏。等做完后面的大题，再回头用第二种方法重新算。因为二叉树性质题通常只要画一棵小树就能找到灵感，时间压力解除后，复杂度会明显下降。

10. 总结与后续学习方向

这道 768 个结点的完全二叉树求叶子数，看似只有数字和公式，实际上把完全二叉树最核心的几条性质都串了起来。度数关系告诉你 n0 = n2 + 1，完全二叉树结构告诉你 n1 只能取 0 或 1，层序编号告诉你叶子结点从 ⌊n/2⌋ + 1 开始。三个角度指向同一个答案：384。

建议收藏本文，复习的时候把三种方法分别推一遍，再用代码跑一遍。推完这道题，你可以继续挑战这些方向：

• 完全二叉树的数组存储与堆排序的关系；
• 由完全二叉树的层序序列还原树结构；
• 已知叶子结点所在层数，求总结点数的最大最小值；
• 二叉树的遍历序列到唯一二叉树的还原；
• 平衡二叉树、哈夫曼树与完全二叉树的性质对比。

这些考点看起来分散，底层还是“树”这一章的基本功。把一棵树的度、结点数、深度、路径这几个概念吃透，后面学图、学排序都会轻松很多。下次再看到类似的题目，别急着套结论，先问自己一句：这个结论我能现场推出来吗？能推出来，才算真正掌握。