遞歸 - 二叉樹

Question

我有這個代碼來找到二叉樹的直徑。 二叉樹的直徑：樹的直徑（有時稱爲寬度）是樹中兩棵樹葉之間最長路徑上的節點數。

我想了解下面的代碼和一般的遞歸。我試圖用這個簡單的樹幹運行。我明白什麼時候root的高度會變成1（Max（0,0）+1），然後返回Math.Max（0 + 0 + 1，Max（0,0））。我的理解是，它將根據此返回值將ldiameter設置爲1，而root = 10。這是正確的嗎？此時lh變爲1.它如何變爲1？另外，如果你可以幫助我幹一步一步地運行這個簡單的樹，這將是非常有用的。

10 
/ \ 
20 30 


public int FindDiameter_util(Node root, ref int height) 
     { 
      /* lh --> Height of left subtree 
      rh --> Height of right subtree */ 
      int lh = 0, rh = 0; 

      /* ldiameter --> diameter of left subtree 
       rdiameter --> Diameter of right subtree */ 
      int ldiameter = 0, rdiameter = 0; 
      if (root == null) 
      { 
       height = 0; 
       return 0; /* diameter is also 0 */ 
      } 
      /* Get the heights of left and right subtrees in lh and rh 
       And store the returned values in ldiameter and ldiameter */ 
      ldiameter = FindDiameter_util(root.left, ref lh); 
      rdiameter = FindDiameter_util(root.right, ref rh); 

      /* Height of current node is max of heights of left and 
       right subtrees plus 1*/ 
      height = Math.Max(lh, rh) + 1; 

      return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 
     } 

Answer 1

最後行最重要的位置：

return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 

有3例爲當前的樹：

1）最長簡單路徑（在currenet樹）在左子樹

2）右子樹中最長的簡單路徑（用於currenet樹）

3）lo最簡簡單路徑由3部分組成：從左邊子樹中最深的節點到根節點的路徑，當前節點，右邊子樹中從根節點到最深節點的路徑。

我們可以遞歸計算3個可能的直徑，然後選擇它們的最大值。

Answer 2

讓我們通過您簡單的樹遞歸：

[]  <---- root 
/ \ 
[] [] <---- children 

當函數最初叫，root == 0將是真實的，所以輸入高度被初始化爲0：

[h=0]  <---- root 
/ \ 
    [] [] <---- children 

然後你會設置左側和右側子樹根部的高度爲0：

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     []  []   <---- children 

然後y OU遞歸左邊的孩子，在lh通過其高度參數：

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     [h=0] []   <---- children 

左子將初始化其高度的變量爲自己的左，右子樹：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

然後左子會嘗試在自己的左子樹上進行遞歸（即使沒有一個子樹;這是null）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
     /
     null 

在這個空節點，我們承認它是這樣，返回0，走回到父，lh被設置爲0（再次，所以沒有變化）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

然後我們遞歸的右子樹，但它也爲空：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
       \ 
      null 

所以我們返回0 FO [R其高度父，這臺rh到0（再次）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

到目前爲止，頗爲無趣。但是現在我們知道了子樹的高度，我們可以計算當前樹的高度爲max(lh, rh) + 1，這給了我們這個葉子的高度爲1（一棵只有根的樹的高度爲1，所以它是有意義的一個只有根的子樹具有高度1）。

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

然而，h在這個水平實際上是在根lh的引用，所以它也成爲1：

 [h = 0, lh = 1, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

現在左子樹做，所以我們遞歸右側子樹以同樣的方式（詳細內容略）：

  [h = 0, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

現在，我們已經遞歸兩個子樹，我們返回到根，現在誰知道

height = Math.Max(lh, rh) + 1; 

是

height = Math.Max(1, 1) + 1 = 2 

所以根得到其高度設定爲2：

  [h = 2, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

其左和右子樹（均爲 1），因此它可以計算的高度

Answer 3

遞歸是一種基於堆棧的方法。函數的遞歸調用將比發行者更早執行。如果您考慮函數組合的概念，您可以更容易理解遞歸。讓我們來看看下面這個例子函數調用：

f(g(x)) 

正如你所看到的，f參數是g(x)，這意味着一個執行f(g(x))前g(x)需要首先計算，因此g(x)是f(g(x))的依賴。現在，假設g是f一樣，所以你打電話

f(f(x)) 

以類似的方式，f(x)是f(f(x))的依賴，因爲你不能沒有具有f(x)結果計算f(f(x))。

如果你明白這個純粹的數學概念，那麼下一步就是將算法添加到f作爲上下文。在編程中，f(f(x))不一定只是一個計算，但可能會發生一些狀態更改。

下一步是瞭解重複遞歸的概念。在我們的情況下，我們不知道應該在FindDiameter_util之內調用FindDiameter_util多少次，因爲它適用於任何樹。所以，讓我們稍微分析一下這個功能。

事實：

• 葉節點的事實，root == null，這是結束標誌以及識別（參見return）
• 高度葉節點中的0
• 在非瑣碎的情況下，當節點不是葉節點，任務分爲兩個子任務（左子樹和右子樹）
• 當計算的子任務的結果，那麼子大樹+ 1（我們加上當前節點）的樹是最大h八

這裏使用的策略叫做Divide et Impera。這是由以下幾個階段組成： - 劃分任務成相似，但更小的子任務，直到你到達平凡 - 征服的結果，得到響應，逐步更復雜的子任務，直到你得到的回答最初的問題

在我們的例子中，算法總之是從根到葉子，直到在所有子樹中達到平凡，這是由root == null的結束符號決定的，然後使用平凡的答案來得到答案到下一個微不足道的問題。所以，你要從根到葉去劃分，然後從葉子到根部去征服。