LeetCode 110. 平衡二叉樹：遞歸求解詳解

題目概述

給定一棵二叉樹，判斷它是否為高度平衡的二叉樹。根據定義，一棵高度平衡二叉樹要求每個節點的左右子樹高度差不超過 1。

核心思路：後序遍歷 + 剪枝

採用後序遍歷（左、右、根）自底向上計算每個節點的高度。在遞歸返回時，若發現左右子樹高度差超過 1，立即標記全局變量 ok = false，並提前終止後續遞歸，避免不必要的計算。

算法步驟

1. 定義全局標記 boolean ok = true。
2. 編寫遞歸函數 dfs(TreeNode root) 返回以 root 為根的子樹高度。
3. 遞歸基礎情況：若節點為空或 ok 已為 false，返回 0。
4. 遞歸計算左、右子樹高度 ha、hb。
5. 若 |ha - hb| > 1，設置 ok = false。
6. 返回當前子樹高度 max(ha, hb) + 1。
7. 主函數調用 dfs(root) 後返回 ok。

完整 Java 代碼實現

public class BalancedBinaryTree {
    static boolean ok = true;

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        n1.left = n2;
        System.out.println(isBalanced(n1)); // true
    }

    public static boolean isBalanced(TreeNode root) {
        ok = true;
        dfs(root);
        return ok;
    }

    public static int dfs(TreeNode root) {
        if (root == null || !ok) return 0;
        int ha = dfs(root.left);
        int hb = dfs(root.right);
        if (Math.abs(ha - hb) > 1) ok = false;
        return Math.max(ha, hb) + 1;
    }
}

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

複雜度分析

• 時間複雜度：O(n)，每個節點僅被訪問一次。
• 空間複雜度：O(h)，h 為樹高，遞歸棧深度；最壞情況 O(n)（退化為鏈表）。

關鍵點總結

利用後序遍歷特性，將「求高度」與「判斷平衡」合二為一，並通過全局標記實現剪枝，是解決此類樹平衡問題的經典模板。