樹葉上的二叉樹深度

我正在從網站上解決以下問題：「編寫函數以查看二叉樹是否」超平衡「（我們剛製作的新樹屬性）樹是」超平衡「如果任何兩個葉節點的深度之間的差異不大於1「。樹葉上的二叉樹深度

網站檢查兩個節點之間深度差異的方法是先深度優先搜索，然後將每個訪問節點的深度追加到稱爲深度的列表中，只要深度不在列表中：

 if depth not in depths: 
      depths.append(depth) 

      # two ways we might now have an unbalanced tree: 
      # 1) more than 2 different leaf depths 
      # 2) 2 leaf depths that are more than 1 apart 
      if (len(depths) > 2) or \ 
       (len(depths) == 2 and abs(depths[0] - depths[1]) > 1): 
       return False

我不明白的是，爲什麼我們要檢查兩種方式？僅僅檢查是否有兩種以上不同的葉片深度或兩種不同的葉片深度是不止一種分離度就足夠了？爲什麼這兩項檢查有用？

代碼/問題從源頭報價：InterviewCake.com

來源

2015-05-05 randomUser47534

好問題;但由於其更多關於算法（而不是代碼問題），它更適合於[程序員.stackexchange.com]（http://programmers.stackexchange.com） –

@BurhanKhalid自從什麼時候不是合適的地方詢問算法？幫助頁面明確指出算法是一個可以接受的主題... – yurib

請顯示更多代碼。現在'我們現在可能已經關心我了' – inspectorG4dget

你既需要檢查，有點...

第一個顯然是不夠的，因爲你可以有len(depths)==2以及兩者之間的區別>1。

第二個條件，因爲它寫，只能工作，如果len(depth)正好是2。你可能只有後一種情況，但是你需要遍歷depth列表中的所有項目。

所以基本上它是這樣設計的，儘可能高效。您可能會認爲這是過度優化的情況，因爲depths列表的長度永遠不會大於3，這也是此檢查將執行的最大數量。

我會用類似max(depths) - min(depths) > 1的東西，這是更具可讀性和直觀性，並且對性能的影響可以忽略不計。

來源

2015-05-05 05:01:31 yurib

樹葉上的二叉樹深度

回答

相關問題