如何根据叶子节点数求k-ary树节点总数？为何二叉树是2L-1而非四叉树4L-1？

首先要明确：只有满k叉树（所有非叶子节点都恰好拥有k个子节点，且所有叶子节点处于同一层级），才能通过叶子节点数推导总节点数，普通k叉树没有固定的计算公式。

为什么满二叉树的总节点数公式是 2L - 1？ #

设满二叉树的总节点数为N，叶子节点数为L，则非叶子节点数为N - L。
每个非叶子节点恰好有2个子节点，因此所有节点的子节点总数为2*(N - L)。
而总节点数N等于根节点（1个）加上所有子节点的数量，可得方程：

N = 1 + 2*(N - L)

解这个方程：

N = 1 + 2N - 2L
N = 2L - 1

这就是满二叉树总节点数公式的由来。

为什么四叉树不能用 4L - 1 计算？ #

满四叉树的推导逻辑和二叉树一致，但公式不同：
设满四叉树总节点数为N，叶子节点数为L，非叶子节点数为N - L。
每个非叶子节点有4个子节点，子节点总数为4*(N - L)，总节点数满足：

N = 1 + 4*(N - L)

解方程：

N = 1 + 4N - 4L
3N = 4L - 1
N = (4L - 1)/3

只有当4L - 1能被3整除时，结果才是整数（比如L=4时，N=(16-1)/3=5，对应根节点+4个叶子的满四叉树，总节点数正确）。如果硬套4L -1，L=4时会得到15，明显不符合实际，因此四叉树不能直接用这个错误公式。

满k叉树的通用公式 #

对于任意满k叉树，总节点数N和叶子节点数L的关系可以通过同样的逻辑推导：

N = 1 + k*(N - L)

整理后得到通用公式：

N = (k*L - 1)/(k - 1)

代入k=2（二叉树），得到N=2L-1，符合已知结论；代入k=4（四叉树），得到N=(4L-1)/3，和之前的推导一致。

内容的提问来源于stack exchange，提问作者Pasha