瞭解如何計算二叉樹的深度

我正在通過職業杯指南作爲通過基本CS主體的速成課程，並堅持計算二叉樹的最小/最大深度的示例。由於這是幾乎所有例子，我認爲我會在這裏發表一個問題。瞭解如何計算二叉樹的深度

該指令旨在實現一種方法，該方法將檢查樹是否平衡。爲了做到這一點，你需要比較最小深度和最大深度，並確保它們之間的差值不大於1。這個原則就像它所得到的一樣簡單。第15行的方法是爲了做到這一點。

但是，我不明白每個幫助程序方法（和minDepth）的返回語句是怎麼回事。如何從root.left或root.right派生出一個數字？是否Math.max功能簡單地假設一個1或0是有值/空節點，或者，由於被指定值（只是Node對象），確實Math.max(maxDepth(root.left), maxDepth(root.right)本身等於0，從而增加由1直到返回值兩個節點都是空的？

如果所以這是用於計算一個樹的最小/最大深度的一般過程：

minDepth =沒有根有孩子嗎？ yes = minDepth = 1，no = minDepth = 0（如果有根目錄）

maxDepth =循環兩個分支，直到找到離根最遠的葉。保持一個櫃檯去確定葉子。

1 public static int maxDepth(TreeNode root) { 
2  if (root == null) { 
3  return 0; 
4  } 
5  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); 
6 } 
7 
8 public static int minDepth(TreeNode root) { 
9  if (root == null) { 
10   return 0; 
11  } 
12  return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
13 } 
14 
15 public static boolean isBalanced(TreeNode root){ 
16  return (maxDepth(root) - minDepth(root) <= 1); 
17 }

來源

2014-07-22 NealR

maxDepth(root.left)返回左子樹的最大深度。
maxDepth(root.right)返回右子樹的最大深度。
這兩個的最大值是最大的子樹深度。
爲根節點添加1，可以獲得樹的最大深度。

想這是樹：

  A 
     B  C 
     D E F G 
    H 
    I

只要看一眼就可以看到的最大深度爲5，最小深度（由路徑ABDHI形成）是3（由多條路徑形成，例如ACG）。

現在，最大深度爲1（對於根A）+兩棵子樹的最大深度。
第一個子樹，其根是B的最大深度爲4（B-D-H-I）。第二個子樹，其根是C的最大深度爲2（C-F）。
最大值（4,2）= 4
因此整個樹的最大深度爲1個+ MAX（4,2）= 5。

如果我們用字母在我的樣本樹來表示子植根於這些節點的樹木，我們得到：

maxDepth(A) = 1 + max(maxDepth(B) , maxDepth(C)) = 
       1 + max(1 + max(maxDepth(D) , maxDepth(E)), 1 + max(maxDepth(F) , maxDepth(G)) = 
       1 + max(1 + max(1+max(maxDepth(H),0) , 1+max(0,0)), 1 + max(1+max(0,0) , 1+max(0,0)) = 
       1 + max(1 + max(1+max(1+max(maxDepth(I),0),0) , 1), 1 + 1) = 
       1 + max(1 + max(1+max(1+max(1+max(0,0),0),0) , 1), 1 + 1) = 
       1 + max(1 + max(1+max(1+max(1,0),0) , 1), 2) = 
       1 + max(1 + max(1+max(2,0) , 1), 2) = 
       1 + max(1 + max(3 , 1), 2) = 
       1 + max(4, 2) = 
       1 + 4 = 
       5

同樣，對於計算最小深度，你算算兩個（左和右）子樹的最小深度，以最小的兩個，並添加1爲根。

來源

2014-07-22 22:33:03 Eran

這就是我沒有遵循的：maxDepth（root.left）如何返回樹的深度？ – NealR

@NealR'maxDepth（root.left）'返回子樹的最大深度，其根是原始樹的根的左子。如果您對遞歸不熟悉，則需要時間來習慣它（並且相信它實際上可行）。 – Eran

對不起，在這裏頭很重，但是這些數字（最大深度）是如何計算的？ – NealR

嗯，這是一個遞歸函數，它檢查樹的兩邊，然後將結果與max或min進行比較。

圖片幫助。

 o go left and right 
    / \ 
(+1)o  o(+1)  
    \  
    o(+1)

所以讓我們把它帶回代碼。

return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

調用堆棧會是這個樣子

// max return 2 
- left +1      
    // max return 1 
    -left 0      
    -right +1 
     // max return 0 
     -left 0     
     -right 0 
- right +1 
    //max return 0 
    -left 0 
    -right 0

Min作品本質上是相同的方式。

來源

2014-07-22 22:39:23 progrenhard

瞭解如何計算二叉樹的深度

回答

相關問題