0110. Balanced Binary Tree - chasel2361/leetcode GitHub Wiki

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:
Given the following tree [3,9,20,null,null,15,7]:
Return true.

Example 2: Given the following tree [1,2,2,3,3,null,null,4,4]:
Return false.

由題目所述，平衡的定義是每個節點的左右子樹高度差 ≤ 1 的狀況，所以必須求解二元樹的高度。我們可以利用遞迴的方式來一層一層進入節點左右子樹，若節點為葉子便回傳 0 ，若否便回傳左右子樹較大值 + 1，可以表示為以下的程式碼

    def maxDepth(root):
        if not root: return 0
        left = maxDepth(root.left)
        right = maxDepth(root.right)
        return 1 + max(left, right)

那考慮到題目的要求：左右子樹高度差 ≤ 1 的狀況，可以在函式裡多加一個判斷，跑完每一個節點之後回傳 balance 的布林值即可

class Solution:
    def __init__(self):
        self.balance = True
            
    def isBalanced(self, root: TreeNode) -> bool:
        depth = self.maxDepth(root)
        print(depth)
        return self.balance
        
    def maxDepth(self, root):
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        if abs(left - right) > 1:
            self.balance = False
        return 1 + max(left, right)

但這樣寫又覺得做了白工，畢竟balance不會用到，所以在更進一步的改進程式，因為二元樹的高度只要存在，就一定是正整數，所以如果以 -1 來表示不平衡的話就不需要使用 balance 變數了

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(root):
            if not root: return 0
            left = check(root.left)
            right = check(root.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)
        return check(root) != -1

這樣寫的時間以及空間複雜度都是 O(N)