二叉樹的遞歸代碼流

我想了解這個遞歸程序，逐步瞭解每次調用該函數時會發生什麼，但是要確保代碼流是否我認爲是正確的。二叉樹的遞歸代碼流

public static int checkHeight(TreeNode root) { 
     if (root == null) { 
      return 0; // Height of 0 
     } 

     /* Check if left is balanced. */ 
     int leftHeight = checkHeight(root.left); 
     if (leftHeight == -1) { 
      return -1; // Not balanced 
     } 
     /* Check if right is balanced. */ 
     int rightHeight = checkHeight(root.right); 
     if (rightHeight == -1) { 
      return -1; // Not balanced 
     } 

     /* Check if current node is balanced. */ 
     int heightDiff = leftHeight - rightHeight; 
     if (Math.abs(heightDiff) > 1) { 
      return -1; // Not balanced 
     } else { 
      /* Return height */ 
      return Math.max(leftHeightJ rightHeight) + 1; 
     } 
    } 
    public static boolean isBalanced(TreeNode root) 
    { 
     if (checkHeight(root) == -1) 
     { 
      return false; 
     } 
     else 
     { 
      return true; 
     } 
    }

實施例：

當程序運行併到達線checkHeight（root.left）它現在有元件2（root.left）所以這得到遞歸調用和疊層具有執行頓住了，像

|checkHeight(2)|

，然後直到它到達最左邊的元素到底有

|checkHeight(7)| 
|checkHeight(4)| 
|checkHeight(2)|

| checkHeight（7）|彈出leftHeight = 0 rightHeight = 0.

運行時| checkHeight（4）| - > leftHeight = 1，rightHeight = 0

| checkHeight（2）| - > leftHeight = 2，rightHeight = 1（因爲它運行| checkHeight（5）|）

一旦完成，它將返回：Max（2,1）+1 = 3這將是leftHeight的值。

我的理解是否正確？希望我不會混淆步驟。在此先感謝

來源

2015-06-29 Kar

這是用什麼語言編寫的，你可能想編輯標籤來包含它。 – hellyale

我想用當前的代碼你可能會在這裏有一個無限循環。不是100％肯定... – hellyale

我添加了語言。我還沒有調試代碼，但仍然一步一步地通過左側子集，我沒有遇到它將無限循環的情況。我會交叉檢查。 – Kar

既然你都沒有問一個具體問題，它可以在代碼方面來回答，我可以這樣說：

以遞歸的關鍵是不要遵循每一個調用和堅持調用迷宮，它正在讀代碼（用於遞歸調用），並且相信遞歸調用應該做什麼，它應該做什麼。更好地確定單個調用它正在做什麼的正確性。然後你可以直接跳過所有「類似」的調用直到結束（如7這裏）

另一件事是基本規則，必須有一個條件，方法返回 - 基本情況無限循環）

同時考慮到這些事實，我認爲你是對與步驟全力以赴（我也跟着通過調用可以肯定的）

提示：您可以隨時使用斷點在調試中檢查整個親而不是手動轉換。畢竟，這是調試的目的。

來源

2015-06-29 04:49:27

你確實是對的..只是想確定一下，如果我在調試之前把它放在紙上了。感謝您提供的信息並驗證步驟的正確性。 – Kar

二叉樹的遞歸代碼流

回答

相關問題