对“一棵有124个叶节点的完全二叉树，最多有多少个结点”的思考

在网上看到这个问题，在讨论答案到底是248，还是247，评论清一色地认为是247，但我觉得答案是248

先再读一遍题目，里面有“最多”两个字，也就是说能满足条件的完全二叉树不止一种，要找出结点最多的那个

评论里的人几乎都认为答案唯一且为247，评论里的观点是：非叶节点数目 = 叶节点+1

这个观点并不是完全正确的，它需要加上一个前提，就是完全二叉树的最右非终结结点的子树个数是二

下面我按照最右非终结结点的子树是二和一两种情况进行分析：

一、最右非终结结点的子树个数是二

除去第n层的全部结点数：$2^{n-1} - 1$2n−1−1

总结点数：$2^{n-1} - 1+S$2n−1−1+S
由此，可以得到:非叶节点数 = 总结点数 $-S-T$−S−T = $2^{n-1}-T-1$2n−1−T−1——————1

第n-1层结点数：$S/2 +T$S/2+T、$2^{n-2}$2n−2
由此，得到等式：$S/2 +T=2^{n-2}$S/2+T=2n−2
将等式变型得到：叶结点数=$S+T=2^{n-1}-T$S+T=2n−1−T——————————————2

将1,2两式联立，得：非叶节点数目 = 叶节点+1

二、最右非终结结点的子树个数是一

除去第n层的全部结点数：$2^{n-1} - 1$2n−1−1

总结点数：$2^{n-1} - 1+S$2n−1−1+S
由此，可以得到:非叶节点数 = 总结点数 $-S-T$−S−T = $2^{n-1}-T-1$2n−1−T−1——————1

第n-1层结点数：$（S+1）/2 +T$（S+1）/2+T、$2^{n-2}$2n−2
由此，得到等式：$（S+1）/2 +T=2^{n-2}$（S+1）/2+T=2n−2
将等式变型得到：叶结点数=$S+T=2^{n-1}-T-1$S+T=2n−1−T−1————————————2

将1,2两式联立，得：非叶节点数目 = 叶节点

最终结论：
当完全二叉树的最右非终结结点子树个数为一时，非叶节点数目 = 叶节点；
当完全二叉树的最右非终结结点子树个数为二时，非叶节点数目 = 叶节点+1

所以，再回到题目本身，我们也要分两种情况讨论：
1.最右非终结结点子树个数为二时，非叶结点数$=124-1=123$=124−1=123
二叉树结点总数$=124+123=247$=124+123=247
$S=18,T=7$S=18,T=7
第n-1层结点数量为：$16$16
符合完全二叉树的特点

2.最右非终结结点子树个数为二时，非叶结点数$=124$=124
二叉树结点总数$=124+124=248$=124+124=248
$S=19,T=6$S=19,T=6
第n-1层结点数量为：$16$16
符合完全二叉树的特点

又因为题目要求最大总结点数，取第二种情况，答案：$248$248