如何找到二叉樹的高度，如果我有節點總數

Question

我知道樹中的節點總數。用這個如何找到樹的高度？

Answer 1

如果你有一棵平衡樹，那麼高度（層數）就是上限（lg（n + 1）），其中天花板總是舍入到下一個最高整數，而lg是以2爲底的對數。如果你有一定類型的自平衡樹（它們並不總是完全平衡的，但高度平衡），那麼也可以給出樹的高度的信息界限。如果你只是假設一個任意的二叉樹（比如說，每個內部節點有兩個孩子），那麼高度可能會高達（n-1）/ 2，例如如果你有一棵看起來像梳子的樹。

Answer 2

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 

欲瞭解更多信息：Click this link