題目出處

110. Balanced Binary Tree

難度

easy

個人範例程式碼

# 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:
        return self.isBalanced_and_get_height(root)[0]


    def isBalanced_and_get_height(self, root):        
        # end of recursion
        if not root:
            return True, 0

        # split
        left_is_balanced, left_height = self.isBalanced_and_get_height(root.left) 
        right_is_balanced, right_height = self.isBalanced_and_get_height(root.right)

        # define
        if not (left_is_balanced and right_is_balanced):
            return False, -1

        if abs(left_height - right_height) > 1:
            return False, -1

        return True, max(left_height, right_height)+1       

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

正常直接的想法是，我們的「所有子樹都必須要是 balanced」，
因此直覺會需要 recursion。

但因為要決定這個結果，我們還需要知道「當前子樹的最大高度」，
設計時，我們可以同時回傳「子樹的答案」+「當前子樹的最大高度」

input handling

一同在 dfs 內處理

Boundary conditions

如果沒有 root，結束遞迴

Reference

• 平衡二叉树 · Balanced Binary Tree