110 Balanced Binary Tree

thoughts

• 平衡樹定義：每個節點的左右子樹高度差 ≤ 1
• 遞迴計算高度：若某個子樹不平衡，回傳 -1

kotlin

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

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

follow up

• 如果樹節點很多（例如上百萬），遞迴可能會 stack overflow，要不要改成 迭代？
• 如果只需要判斷是否平衡，不需要高度，能否提前剪枝？