平衡二叉樹判斷：遞歸後序遍歷兩種寫法對比

題目

給定二叉樹，判斷是否為高度平衡：每個節點的左右子樹高度差 ≤ 1。

解法一：引用傳遞高度 + 布爾返回

bool isBalancedTree(TreeNode* root, int& depth) {
    if (!root) { depth = 0; return true; }
    int leftDepth = 0, rightDepth = 0;
    bool leftOk = isBalancedTree(root->left, leftDepth);
    if (!leftOk) return false;
    bool rightOk = isBalancedTree(root->right, rightDepth);
    if (!rightOk) return false;
    if (abs(leftDepth - rightDepth) > 1) return false;
    depth = max(leftDepth, rightDepth) + 1;
    return true;
}
bool isBalanced(TreeNode* root) {
    int depth = 0;
    return isBalancedTree(root, depth);
}

要點：必須用引用 int& depth 向上傳遞高度，同時用返回值傳遞是否平衡。滿足三個條件：左平衡、右平衡、高度差 ≤ 1。

解法二：特殊返回值 -1 表示不平衡（更巧妙）

int getDepth(TreeNode* root) {
    if (!root) return 0;
    int left = getDepth(root->left);
    int right = getDepth(root->right);
    if (left == -1 || right == -1 || abs(left - right) > 1) return -1;
    return max(left, right) + 1;
}
bool isBalanced(TreeNode* root) {
    return getDepth(root) != -1;
}

優勢：單一返回值同時攜帶「高度」與「是否平衡」信息，代碼更簡潔，無需額外引用參數。

Java 版

public boolean isBalanced(TreeNode root) {
    return check(root) != -1;
}
private int check(TreeNode node) {
    if (node == null) return 0;
    int l = check(node.left), r = check(node.right);
    if (l == -1 || r == -1 || Math.abs(l - r) > 1) return -1;
    return Math.max(l, r) + 1;
}

複雜度

• 時間：O(n)，每節點訪問一次。
• 空間：O(h) 遞歸棧，h 為樹高，最壞 O(n)。

關鍵測試用例

A = {3,9,20,#,#,15,7}  → true
     3
    / \
   9  20
     /  \
    15   7

B = {3,#,20,15,7}      → false
   3
    \
    20
   /  \
  15   7