定叶结点，求结点数

Question

求叶结点为121的完全二叉树的结点个数。我求的是248，但是不对，答案就没有这个选项。我的思路是，树深度为7，把第六层结点分为三类，一类x,子结点为2；二类为y,子结点为1；三类z，子结点为0；设方程2x+y+z=121;x+y+z=64;总结点数为127+2x+y=248-z,取z为0，总结点数为248，我想知道我哪错了？

Answer 1

深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

按你的思路，解得 x = 57，那么 y + z = 7。
根据完全二叉树的性质，子结点为1的节点y只能为1或者0。

若 y = 1，最后一层的叶子节点数为2*57+1=115，节点数为 255-(128-115)=242。

若 y = 0，最后一层的叶子节点为 2*57=114，节点数为 255-(128-114)=241。

Answer 2

一棵完全二叉树，叶节点为121，那么倒数第二层的节点数应该是小于等于121的2^n的最大值，也就是64，此时n=6，整棵树的深度应该是7

再看你列的方程，x是子节点为2的节点数，没有问题
y是子节点为1的节点数，你想想，y是不是只有可能取0或者1？y的取值对叶节点数有影响吗？没有（给一个叶节点加上一个叶节点，这棵树的叶节点数量是不变的），那可以直接取个0，好算
那z也不需要，z就是2^n-x，这道题就是64-x

那这个方程式就简单多了，就是2x+(64-x)=121，x=57，y可能是0或者1

总结点数就是127+57*2+0/1 = 241或242