我认为这个问题在这里是非常不言而喻的，但我正在看第三版的“算法简介”第37页，它说，图2.5中递归树的总级别是lg n+1，但我不明白为什么必须+1有谁能解释一下背后的原因吗？谢谢
最佳答案
这棵树应该有N片叶子一个h级（根是1级）的二叉树最多有2^（h-1）片叶子，因此我们断言2^（h-1）>=n，即h>=lg（n）+1。同时它应该是一个完整的二叉树。一个h级的完整二叉树至少有（2^（h-2）+1）片叶子，即2^（h-2）+1当n=2^k，k+2>h>=k+1，所以h=k+1=lg（n）+1，这就是书中的情况。
更重要的是，当N！=2^k，会有一个k，其中2^k>n>2（k-1），我们有h>=lg（n）+1>k和h总之，k=ceil（lg（n）+1）其中ceil（lg（n）+1）表示不小于lg（n）+1的最小整数。
关于performance - 为什么合并排序的递归树的级别总数为lg n +1？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19652390/