110. Balanced Binary Tree

Easy

Description

給定一棵二元樹，判斷它是否是高度平衡的。高度平衡的二元樹定義為：每個節點的左右子樹高度差不超過 1。

Example:

Input: root = [3,9,20,null,null,15,7] Output: true

Intuition#

自底向上計算高度，一旦發現任何節點不平衡就提前回報 -1。

平衡的定義是遞迴的：根平衡 + 左右子樹都平衡
自頂向下會重複計算高度，自底向上只需一次遍歷

Approaches#

1: Top-Down（自頂向下）#

概念: 對每個節點計算左右子樹高度，檢查差值，再遞迴檢查子樹
時間複雜度: O(n^2)，每個節點都要重新計算高度
空間複雜度: O(n)

class Solution {
    fun isBalanced(root: TreeNode?): Boolean {
        if (root == null) return true
        val diff = Math.abs(height(root.left) - height(root.right))
        return diff <= 1 && isBalanced(root.left) && isBalanced(root.right)
    }

    private fun height(node: TreeNode?): Int {
        if (node == null) return 0
        return 1 + maxOf(height(node.left), height(node.right))
    }
}

⭐ 2: Bottom-Up（自底向上）#

概念: 遞迴計算高度時，若發現不平衡就回傳 -1 作為標記，提前結束
時間複雜度: O(n)
空間複雜度: O(h)

class Solution {
    fun isBalanced(root: TreeNode?): Boolean {
        return checkHeight(root) != -1
    }

    private fun checkHeight(node: TreeNode?): Int {
        if (node == null) return 0
        val left = checkHeight(node.left)
        if (left == -1) return -1
        val right = checkHeight(node.right)
        if (right == -1) return -1
        if (Math.abs(left - right) > 1) return -1
        return 1 + maxOf(left, right)
    }
}

🔑 Takeaways#

Pattern: 自底向上（Bottom-Up）比自頂向下（Top-Down）更高效，避免重複計算
關鍵技巧: 用特殊回傳值（如 -1）作為「不合法」的標記，可以在遞迴中提前終止