LeetCode 110. 平衡二叉樹：後序 DFS 判定高度差不超過 1 的最優解法

LeetCode 110. 平衡二叉樹：後序 DFS 判定高度差不超過 1 的最優解法

判斷二叉樹是否為高度平衡：每個節點的左右子樹高度差不超過 1。本文提供 O(n) 時間、O(h) 空間的後序遞歸解法，利用哨兵值 -1 實現剪枝。

題目定義

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

核心代碼

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0; // 空樹高度 0

        int left = dfs(node.left);
        if (left == -1) return -1; // 左子樹不平衡，直接向上傳遞

        int right = dfs(node.right);
        if (right == -1) return -1; // 右子樹不平衡

        if (Math.abs(left - right) > 1) return -1; // 當前節點不平衡

        return Math.max(left, right) + 1; // 返回當前子樹高度
    }
}

演算法解析

對比：自頂向下遞歸（低效）

// 低效寫法：每個節點重複計算子樹高度 → O(n log n) 甚至 O(n²)
public boolean isBalancedSlow(TreeNode root) {
    if (root == null) return true;
    return Math.abs(height(root.left) - height(root.right)) <= 1
        && isBalancedSlow(root.left)
        && isBalancedSlow(root.right);
}
private int height(TreeNode n) {
    return n == null ? 0 : Math.max(height(n.left), height(n.right)) + 1;
}

測試用例

// 平衡樹
    3
   / \
  9  20
    /  \
   15   7
// → true

// 不平衡樹
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
// → false (節點 2 左右高度差 2)

擴展：迭代法（後序遍歷 + 顯式棧）

避免深度遞歸棧溢出，可用雙棧或單棧 + 訪問標記實現後序迭代，邏輯相同但代碼較繁瑣。面試中遞歸寫法通常可接受，除非明確要求非遞歸。

總結

• 平衡二叉樹判定核心是「高度計算與平衡檢查合一」。
• 哨兵值 -1 是經典剪枝技巧，亦適用於「判斷是否為 BST」、「計算直徑」等自底向上樹形 DP 問題。
• 掌握後序遍歷模板，舉一反三解決大多數樹形遞歸問題。