如果知道二叉树的节点数，如何找到它的最小高度？

Question

设 n 为二叉树的节点数，那么找出二叉树的最小高度的通用函数项是什么？

我认为n=floor(log2(n))+1。但是，我想，我错了。

Answer 1

请记住这个概念

为了使高度最小，您必须给出每个级别可以容纳的最大节点数

因此对于高度为 h 的树，该树总共可容纳的最大节点数 = 2^(h+1)-1，因此 n<=2^(h+1)-1
求解后可得
h>=log(n+1)base2 -1
现在要确定 log 的下限或上限，请像这样思考

如果我的登录数是 3.56.. 那么这意味着直到高度 3 每个级别都被完全消耗，最后一个级别还没有完全填满。正如高度的定义所说，它是从根到叶子的最长路径，所以在高度中我们也将包括最后一层。

因此 ceil 将优先于 Floor。通过这种方法，您还可以找到 m 叉树。