为什么每层的节点数是 2 的幂？

适用条件

• 递推关系为 $f(n) = f(n-1) + f(n-2)$，生成一棵二叉树。
• 层级从 1 开始编号。
• 为了理论估算，将树视为满二叉树进行计数。

理解与推导

1. 将根节点识别为第 1 层，包含 1 个节点（$2^0$）。
2. 观察到每个节点在下一层分裂成两个子节点。
3. 计算第 2 层的节点数为 2（$2^1$），第 3 层为 4（$2^2$），第 4 层为 8（$2^3$）。
4. 将该规律推广，得出第 $k$ 层对应 $2^{k-1}$ 个节点的结论。

例子

讲师从上到下逐层指点：第二层有 2 个节点，第三层有 4 个节点，第四层有 8 个节点，并依次在树旁写下 $2^0$、$2^1$、$2^2$ 和 $2^3$。数学推理很直接：每次递归调用分裂成两个子调用，所以每层的节点数呈 2 的幂增长。

容易误解的地方

• 假设每层的节点数在整个树中是恒定的。
• 混淆层级索引 $k$ 与指数，忘记第 1 层对应的是 $2^0$。

观看对应讲解

继续追问

• 如何通过对每层节点数求和得出 $O(2^n)$？
• 基本情况 $f(1) = f(2) = 1$ 在这个分析中起什么作用？
• 这个递归算法的时间复杂度是多少？