查找二叉樹的最大深度

Question

public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

public class Solution { 
    public int maxDepth(TreeNode root) { 
     TreeNode focusNode = root; 
     TreeNode focusNode2 = root; 
     int count = 0; 
     int count1 = 0; 
     boolean a = true; 
     while (a) { 
      if (focusNode != null) { 
       count++; 
       focusNode = focusNode.left; 
      } 
      if (focusNode2 != null) { 
       count++; 
       focusNode2 = focusNode2.right; 
      } else { 
       a = false; 
      } 
     } 
     return Math.max(count,count1); 
    } 
} 

我很困惑爲什麼我寫的代碼無法給出預期的輸出。而且我也對最大深度的定義感到困惑。僅僅考慮左邊排列的所有節點還是排列在右邊的所有節點，都會發現最大深度？

Answer 1

我不確定你是在談論樹的高度還是節點的深度。
這裏是高度和深度的定義。

節點的高度 - 節點的高度是該節點和葉子之間最長的向下路徑上的邊的數量。

深度-節點的深度是從節點到樹的根節點的邊的數量。

   R 
      /\ 
       A B 
      /\/\ 
      C D E F 
       \ 
       G  

例如：
爲節點R的深度爲0，高度爲3
爲節點G的深度是3和高度爲0

讓假設你發現樹的高度。
爲什麼你的程序無法獲得你想要的結果？
這是因爲你的代碼沒有遍歷樹中的所有節點

讓我們用樹圖爲例：
在你的循環將首先讓focusNode，focusNode2 =節點R

focusNode R> A> C
focusNode2 R> B>˚F>終止

內樹中所有子節點沒算，如果你的樹是不是一個完美的二叉樹，那麼你會得到錯誤的答案。

建議你可以閱讀如何遍歷像預購Travesal
https://en.wikipedia.org/wiki/Tree_traversal

Answer 2

你不是遍歷整個樹一樹的一些算法。你只在最左邊和最右邊的路徑上跑。

通常情況下，遞歸是你的朋友與二叉樹，因爲每個節點可以簡單地和孤立地處理。

定義爲節點類​​方法，即利用這些事實：

• 空孩子的深度爲零
• 非空孩子的深度是通過調用發現其​​方法（即遞歸）
• this節點的深度是其子的深度最大，加1（所以它本身計數）

實現它並在根節點上調用​​以查找樹的最大深度。相應實現的遞歸性質將貫穿整個樹。