非遞歸程序找到二叉樹的最小高度

我知道可以編寫遞歸代碼來查找最小高度。但是對於一棵很大的樹（就像左邊的百萬節點和右邊的一個節點一樣） - 這種方法並不好。所以，請讓我知道如果下面的代碼是好的，它使用BFS： -非遞歸程序找到二叉樹的最小高度

if (root == null) 
    { 
     return 0; 
    } 

    Queue<Node> queue = new Queue<Node>(); 
    queue.Enqueue(root); 
    int min = 0; 

    while (queue.Count > 0) 
    {     
     Node temp = queue.Dequeue(); 

     if (temp.LeftChild == null) 
     { 
      return ++min; 
     } 
     if (temp.LeftChild != null) 
     { 
      ++min; 
      queue.Enqueue(temp.LeftChild); 
     } 

     if (temp.RightChild == null) 
     { 
      return ++min; 
     } 
     if (temp.RightChild != null) 
     { 
      ++min; 
      queue.Enqueue(temp.RightChild); 
     } 
    } 

    return 0;

因此，對於像

樹上面返回1，（按照樓（日誌（N））？

感謝。

來源

2012-08-12 parsh

對於百萬節點的情況，遞歸怎麼樣不好呢？你擔心運行時性能，耗盡堆棧還是其他？ – razeh 2012-08-12 20:53:04

它性能更好（＆耗盡堆棧） - 如果我能快速找到葉節點，爲什麼我必須遍歷整個樹。（返回1 + Math.Min（GetMin（root.LeftNode），GetMin（root.RightNode））; – parsh 2012-08-12 21:07:05

的想法是完美的，但代碼仍然可以做得更好一點。

爲什麼每次出廠時都增加分鐘數？而且你做了兩次，這是兩倍更糟:)如果你將這個變量作爲節點計數器，那麼它也是不正確的，因爲你沒有計算根元素。因此必須以其他方式調用，而不是分鐘。
你爲什麼要檢查孩子是否爲空？如果陳述破壞了管道，它們的數量必須最小化。

接下來的想法。如果所有節點都有子節點，我們稱之爲相同級別節點的行full。然後分高度是樹中的全行行的計數。它等於2最接近力指數爲項目中的所有全行數+ 1 A碼：

if (root == null) 
{ 
    return 0; 
} 

Queue<Node> queue = new Queue<Node>(); 
queue.Enqueue(root); 
int nodesCount = 0; 

while (queue.Count > 0) 
{     
    Node temp = queue.Dequeue(); 

    if (temp.LeftChild == null || temp.RightChild == null) 
    { 
     return Floor(Log(nodesCount + 1)/Log(2)); // It can be made much better using, for example, bitwise operations but this is not the question`s topic 
    } 

    ++nodesCount; 
    queue.Enqueue(temp.LeftChild); 
    queue.Enqueue(temp.RightChild); 
} 

return Infinity; // :)

來源

2012-08-13 15:27:52 dvvrd

謝謝你的soln。我的不好，在發佈之前沒有清理代碼，請記住。，編寫乾淨的代碼的好處:-)。但我有一個後續q，爲什麼上面的樹的遞歸返回值= 2。如果我錯了，請糾正我。 if（root == null）return 0; return Math.Floor（1 + Math.Min（MinHeight（root.LeftChild），MinHeight（root.RightChild）））; – parsh 2012-08-14 08:18:31

@parsh：這是因爲你步入1個額外的等級。如果當前子節點爲null，則返回0。這是錯誤的觀點，因爲當前孩子至少沒有一個孩子時，我們的身高爲0。這就是爲什麼當你進入第三節點時得到高度1，當回到根節點時得到2 – dvvrd 2012-08-14 08:27:24

使用2堆棧做一個「Z形」遍歷。計算您需要翻轉「leftToRight」標誌的次數。

來源

2012-08-14 07:13:45

非遞歸程序找到二叉樹的最小高度

回答

相關問題