【参考答案】讨论7.1 最小X为什么不是1？

陈越发表于2019年07月28日

一般的误解是：既然H是树高，X所在的一层也包含在树的范围内，要保证树的高度不变，底层的X至少应该是1。 然而注意到公式1计算H的时候，由于是向下取整，所以当最底层有结点的时候，得到的并不是真正的树高，而是除去底层结点后的完美二叉树的树高。当二叉树正好是完美的时候，H才是真正的树高，而此时X那一层不存在，也即对应了X=0的情形。