[Leetcode] Balanced Binary Tree

問題：給一個二叉樹，寫一個算法判斷這個樹是不是balanced。   Solution #1.   第一次遇到這個問題時我的解法，如下：   復制代碼 public class Solution {     public boolean isBalanced(TreeNode root) {         if(root == null){             return true;         }                  int depthOfLeft = getDepth(root.left, 1);         int depthOfRight = getDepth(root.right, 1);                  if(Math.abs(depthOfRight-depthOfLeft) > 1){             return false;         }else{             return isBalanced(root.left) && isBalanced(root.right);         }     }          private int getDepth(TreeNode tree, int currentDepth){         if(tree == null){             return currentDepth;         }         return Math.max(getDepth(tree.left, currentDepth+1),                  getDepth(tree.right, currentDepth+1));     } } 復制代碼 寫了一個getDepth()函數，訪問每個節點都要調用一次這個函數。這個Solution也通過了leetcode的驗證程序，但是後來想了想，I can do better.   下面是我對此算法時間復雜度的分析，當整棵樹有N個節點時，時間復雜度是O(N*logN).           Solution #2:   今天我想出了更好的Solution，只需一遍DFS，可以將時間復雜度優化到O(N)，但是空間復雜度同樣是O(N).   復制代碼 public class CheckTreeBalanced {          HashMap<TreeNode, Integer> heights = new HashMap<TreeNode, Integer>();       // The idea is to run DFS once     boolean isBalanced(TreeNode root){         if(root == null){             heights.put(null, 0);             return true;         }                  if( isBalanced(root.left) && isBalanced(root.right) ){             if(Math.abs(heights.get(root.left) - heights.get(root.right)) > 1){                 return false;                              }else{                 int currentHeight = Math.max(heights.get(root.left),                         heights.get(root.right)) + 1;                 heights.put(root, currentHeight);                 return true;             }                      }else{             return false;         }     } } 復制代碼     Solution #3:   Cracking the coding interview上看到另一種解法，time complexity O(N), space complexity O(logN). 之所以占用logN的空間是因為這是DFS的特點，整棵樹的高度H=logN，DFS必然會占用O(H), explicitly or implicitly.   該算法的思路是基於Solution #1的一種改進，把每個節點的height信息和isBalanced信息融合到一起個變量中：   如果該變量>=0，那麼該節點是balanced並且該變量就是節點的height；   如果該變量<0，那麼該節點是unbalanced，但同時我們失去了它的height信息。   復制代碼 public class CheckTreeBalanced2 {          public int checkHeight(TreeNode root){         if(root == null){             return 0;         }                  int leftHeight = checkHeight(root.left);         if(leftHeight == -1){             return -1;         }                  int rightHeight = checkHeight(root.right);         if(rightHeight == -1){             return -1;         }                  int heightDiff = leftHeight - rightHeight;         if(Math.abs(heightDiff) > 1){             return -1;         }else{             return Math.max(leftHeight, rightHeight);         }     }          public boolean isBalance(TreeNode root){         if(checkHeight(root) == -1){             return false;         }else{             return true;         }     } }