algorithm - 如果我有节点总数，如何找到二叉树的高度

Question

我知道树中的节点总数。使用这个如何找到树的高度？

Answer 1

Create a queue.
Push root into the queue.
height = 0
Loop
    nodeCount = size of queue

        // If number of nodes at this level is 0, return height
    if nodeCount is 0
        return Height;
    else
        increase Height

        // Remove nodes of this level and add nodes of 
        // next level
    while (nodeCount > 0)
        pop node from front
        push its children to queue
        decrease nodeCount
       // At this point, queue has nodes of next level

欲了解更多信息：点击此链接

Answer 2

如果你有一个平衡树，那么高度（层数）是上限（lg（n+1）），其中上限总是四舍五入到下一个最高整数，lg 是以 2 为底的对数。如果您有某些类型的自平衡树（它们并不总是完全平衡，而是高度平衡），那么也可以给出树高度的信息界限。如果您只是假设一棵任意二叉树（例如，每个内部节点都有两个子节点），那么高度可能高达 (n-1)/2，例如，如果您有一棵看起来像梳子的树。