題目

  • 題目連結
  • 目標函式 : isBalanced(root)
    • Input : root: TreeNode
    • Output : bool

解題概念

  • 題意 : 給予一 Binary Tree，判斷其是否為 Height-balanced
  • Height-balanced binary tree : 為一 Binary Tree，其兩邊子樹的深度相差小於 1

我的寫法

  • 想法 : 我採用遞迴的方式，使用 getHeight() 去獲取該子樹的高度
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def isBalanced(self, root):
        
        if not root: return True

        def getHeight(node):
            if node == None : return 0
            return max(getHeight(node.left), getHeight(node.right)) + 1 
        
        if abs(getHeight(root.left) - getHeight(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right):
            return True
        return False
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n^2)}$
    • Runtime: 54 ms (faster than 11.50%)
    • Memory Usage: 18.3 MB (more than 50.31%)

解答 or 其他優秀寫法

  • 想法 : 把原本 getHeight() 與 isBalance() 融合在一起
    • 如果發現 node 兩側子樹的高度不平衡 (= -1)，則直接 return -1
    • 否則再去衡量 node 平行狀況
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def isBalanced(self, root):
        
        if not root: return True

        def getHeight(node):
            if node == None : return 0

            left = getHeight(node.left)
            if left == -1: return -1

            right = getHeight(node.right)
            if right == -1: return -1

            if abs(left - right) <= 1:
                return max(left, right) + 1 
            else :
                return -1
        
        return getHeight(root) != -1
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 32 ms (faster than 84.11%)
    • Memory Usage: 18.3 MB (more than 57.80%)