有这样一个面试题：已知哈夫曼树有121个叶子节点，求非叶子节点的个数
没接触过相关概念或者忘了的，我稍微用白话解释下：
哈夫曼树：将N个数据结构当叶子节点，以其某个域的值V作为权重，把这些叶子节点组合成一棵树（N个节点都要存在且仅作为叶子节点），使得所有叶子节点到树根的加权路径和最小，即距离D*V的总和最小 树的度：树中某个节点最多有几个
举例来说，如果给定列表[1,2,3,4,5]，组成一棵度为2的哈夫曼树，有如下步骤：
1、从中选择2个最小的构成一棵树，并计算构成后的树的权，1 + 2 = 3 2、将新构成的树重新加入列表得到：[4,5,3(1,2)] 3、如果新的列表大于2（度），跳转到步骤1，否则剩余节点全部加入一个根节点，完成构建
有了这些基本概念后，如何求解呢，我们先问下GPT看看
GPT-4给出的公式和推导过程如下：
首先，假设一棵度为m的哈夫曼树有n个叶子节点，x个非叶子节点，那么它的总节点数为n+x。 其次，观察这棵树的结构，可以发现除了根节点外，每个非叶子节点都有m个子节点，而每个叶子节点都没有子节点。所以，这棵树的总分支数为xm+0n，也就是xm。 再次，由树的基本性质可知，一棵有k个节点的树，它的分支数等于k-1。 所以，这棵树的总分支数也可以表示为n+x-1。 最后，将上面两个等式联立，得到xm=n+x-1，解得x=⌈(n-1)/ (m-1)⌉。
这个回答有启发意义，但仍然没有解释清楚，至少有两个疑问：
1）每个非叶子节点都有m个子节点吗？2）最后为何要向上取整？
第一个问题的答案显然是否定的，比如叶子节点为4、度为3的哈夫曼树，一定有一个非叶子节点有两个子节点而不是3个；而第二个问题答案是：向上取整就是解决上述例外的。
具体的，我们易得如下两个断言：
1）如果有非叶子节点不满，那么仅有一个不满的非叶子节点；因为同级别合并不改变结果，而向上合并可以减少层级从而减少加权路径总和。
2）不满的非叶子节点的子节点数量只会在[2,m-1]这个闭区间之内，没有只有一个子节点的非叶子节点；因为一个子节点的非叶子节点完全可以被他的子节点直接替换，还能减少一个层级，进而减少加权路径和。
于是，补齐这个不满的节点可得的准确的表达式及其推导形式：
x * m = n + y + x - 1 x = ((n-1)+y)/(m-1)
根据前述两个断言，补齐的y个节点，数量在[0,m-2]闭区间内，可以不需要补齐，但绝对不会补齐m-1个（断言二），但注意y不等于n%m，以叶子节点5、度3的哈夫曼树为例，不需要补齐（第一层3个节点，两个叶子节点，第二层三个叶子节点），而不是需要补齐2个。而补齐的最终目的就是为了让每个非叶子节点可以有m个子节点，所以对(n-1)/(m-1)向上取整即可以达到目的，求出最少满足条件的x。
还有一种利用构建规律来计算的方法，比如每一轮合并后都会从n个节点内先扣除m个节点再加入一个非叶子节点，那么可以用(n-1)/(m-1)再向上取整来计算。这种方式得出的公式一致，但是很难解释n-1以及向上取整。而且，当度大于等于3时，哈夫曼树的构建已经不能直接找M个最小节点合并了，需要加入一些占位节点补齐，例如[1,1,1,1,1,1]这个数列，如果按最小M合并方法，将得到[6,3(1,1,1),3(1,1,1)]这棵非常对称的树，但他的加权路径和12不是最小的，而加入一个占位节点0，得到[0,1,1,1,1,1,1]，再利用最小M个节点合并法，将得到[6,1,2(0,1,1),3(1,1,1)]，他的加权路径和为11，比前面的更小。