給定一棵二元樹，判斷它是否是高度平衡的。高度平衡的二元樹定義為：每個節點的左右子樹高度差不超過 1。
Example:
Input: root = [3,9,20,null,null,15,7] Output: true
Intuition
TIP
自底向上計算高度，一旦發現任何節點不平衡就提前回報 -1。
- 平衡的定義是遞迴的：根平衡 + 左右子樹都平衡
- 自頂向下會重複計算高度，自底向上只需一次遍歷
Approaches
1. Top-Down — O(n^2) / O(n)
- Idea: 對每個節點計算左右子樹高度，檢查差值，再遞迴檢查子樹
- Time:
O(n^2)，每個節點都要重新計算高度 - Space:
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 — O(n) / O(h)
- Idea: 遞迴計算高度時，若發現不平衡就回傳 -1 作為標記，提前結束
- Time:
O(n) - Space:
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）更高效，避免重複計算
- Key trick: 用特殊回傳值（如 -1）作為「不合法」的標記，可以在遞迴中提前終止