解題說明
Balanced Binary Tree
題目描述：給定一棵二元樹，判斷它是否為「高度平衡」二元樹。高度平衡的定義是：對樹中每一個節點，其左右子樹的高度差不超過 1。
解題思路：樸素解法對每個節點各呼叫一次深度計算，導致 O(n²) 重複計算。最佳化方式是將「高度計算」與「是否平衡判斷」合併在同一次後序 DFS 中。定義輔助函式 checkHeight(node) 回傳子樹高度，但若發現某子樹已不平衡，則直接回傳哨兵值 -1，讓父節點立即短路（early termination）並向上傳遞 -1。這樣整棵樹只需一次 O(n) DFS 遍歷即可完成判斷，且能在發現第一個不平衡點時提前結束。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點最多被訪問一次；發現不平衡後不再往下遞迴。
空間複雜度：O(h) — 遞迴堆疊深度等於樹高 h；最壞情況（退化鏈）為 O(n)，平衡樹為 O(log n)。
虛擬碼
1. Define checkHeight(node): a. If node is null, return 0 b. left = checkHeight(node.left) c. If left == -1, return -1 // propagate unbalanced signal d. right = checkHeight(node.right) e. If right == -1, return -1 f. If |left - right| > 1, return -1 // height diff exceeds 1 g. Return 1 + max(left, right) 2. Return checkHeight(root) != -1
其他解法
暴力遞迴 O(n²)：對每個節點分別呼叫 getHeight()，再檢查左右高度差。每次 getHeight 都重新遍歷子樹，導致大量重複計算。程式碼最直觀，但在高度不平衡的大樹上效能差。
BFS 層序遍歷（由下而上）O(n)：先用後序記錄每個節點高度，再用 BFS 驗證每層節點的平衡性。實作較複雜，效能與最佳遞迴相同，通常不採用。
延伸思考
- 若要找出所有不平衡的節點位置（而非只回傳 true/false），如何修改？
- 在 AVL 樹的插入操作中，如何利用類似的高度追蹤機制來決定是否需要旋轉？
- 「高度平衡」與「完全平衡（perfect balance）」有何差異？各自的應用場景為何？