題目:

Given a binary tree, determine if it is height-balanced.

給定一個binary tree,判斷它是否為高度平衡二元樹

在上題我們已經知道高度平衡二元樹的定義是所有兩子樹高度最多相差1的binary tree
在寫這題時我本來有個想法,但我想了很久還是無法實踐
最後我還是直接用定義解去解QQ
不過當我在逛討論區時發現有人將我原初的想法成功實踐,不過待會再提
先看我用定義的解法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
            
        def depth(root): 
            if not root:
                return 0
            return max(depth(root.left),depth(root.right))+1
        
        if abs(depth(root.right)-depth(root.left))<=1:
            return self.isBalanced(root.right) and self.isBalanced(root.left)
        else:
            return False

這裡偷了104.寫出的函數來用
透過遞迴不斷往下偵測各節點的左右子樹高度相差是否超過1
一旦有出現差超過1的狀況就回傳False
最後執行時間61ms(faster than 80.27%)

其實我最初的想法是想改造104.測最大深度的函數
當比兩側子樹大小時順便偵測高度相差是否超過1
但我無法寫出何時該回傳高度何時該回傳布林值的判斷式,所以最後放棄了這個想法
而我在討論區看到的實作出來的人是這樣寫的

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def ans(root):
            if root:
                l=ans(root.left)
                r=ans(root.right)
                if l!=-1 and r!=-1 and abs(l-r)<=1:
                    return max(l,r)+1
                return -1
            else:
                return 0
        return ans(root)!=-1

一旦發現高度相差超過1的情形,就讓測最大深度函式的最終回傳值變為-1
最後只要看結果是否等於-1就知道該樹是否是高度平衡二元樹了
挺巧妙的,是我當初沒想到的辦法
最後執行時間48ms(faster than 97.02%)

那我們下題見