題⽬描述

輸⼊⼀棵節點數為 n ⼆叉樹，判斷該⼆叉樹是否是平衡⼆叉樹。

在這⾥，我們只需要考慮其平衡性，不需要考慮其是不是排序⼆叉樹

平衡⼆叉樹（ Balanced Binary Tree ），具有以下性質：它是⼀棵空樹或它的左右兩個⼦樹的⾼度差的絕對值不超過 1 ，並且左右兩個⼦樹都是⼀棵平衡⼆叉樹。

樣例解釋：

思路及解答

自頂向下遞歸（基礎解法）

平衡樹意味着我們需要對⽐任何在同⼀個根下的左右⼦樹的⾼度差，還記得之前我們計算樹的⾼度麼，使⽤遞歸⽅式來解決，其實這道題與算⾼度差不多，只是兩邊⾼度需要算出⼀個差值。

算法的主要思想：

• 不斷對⽐每兩個節點的左右⼦樹的最⼤⾼度差，注意取差的絕對值，需要⼩於等於1
• 對⽐完左右⼦樹之後，需要遞歸左⼦樹以及右⼦樹進⾏分別判斷，都滿⾜才是平衡樹

public class Solution79 {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        // 當前左右⼦樹是否平衡以及左右⼦樹分別是否平衡
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
            IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 遞歸獲取深度
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

• 時間複雜度 O(nlogn) ：最差情況下，需要遍歷樹所有節點判斷是否平衡，需要O(n)。但是判斷每個節點最⼤⾼度需要遞歸左右⼦樹，需要佔⽤ O(log2n) ，所以總共佔⽤ O(Nlog2n)
• 空間複雜度 O(n) ：最差情況下，也就是樹退化為鏈表時，遞歸需要使⽤ O(n) 的棧空間，嚴格意義上遞歸棧也需要空間。

自底向上遞歸（優化解法）

上⾯的計算，仔細觀察就會發現會有很多重複計算的過程，⽐如下⾯的數，計算⼦樹深度的時候，計算 1 的左⼦樹，和計算 2 的，基本都重複了。

應該如何避免這種重複計算呢？前⾯的是⾃頂向下的⽅式，因為每個節點都得把⼦樹計算⼀遍才需要重複，如果我們從下往上計算，那不就避免了重複計算。後序遍歷，先判斷子樹平衡性，再判斷當前節點，對⽐邏輯如下：

• 如果當前節點為空，⾼度為0
• 如果當前節點的左⼦樹的⾼度為-1，那麼説明不平衡，否則，需要計算右⼦樹⾼度，同樣需要不等於-1，如果兩者的差不符合⼩於等於1，那麼説明它們不平衡，返回-1。通過這樣 -1 異常值就會⼀路返回，到最初的調⽤處，得到不平衡的結果。

public class Solution79 {
    public boolean IsBalanced_Solution(TreeNode root) {
        // 空樹
        if (root == null) {
            return true;
        }
        return getHeight(root) != -1;
    }
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;//空節點高度為0
        }
        // 左⼦樹的⾼度
        int left = getHeight(root.left);
        if (left < 0) {
            return -1;//左子樹不平衡，直接返回
        }
        // 右⼦樹的⾼度
        int right = getHeight(root.right);
        if (right < 0) {
            return -1;//右子樹不平衡，直接返回
        }
        
        // 檢查當前節點是否平衡
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

• 時間複雜度 O(n) ：每個節點計算⼀次
• 空間複雜度 O(n) ：遞歸需要使⽤額外堆棧空間

筆試面試時，建議首選這個方式，效率最優，代碼簡潔

封裝信息法（面向對象思路）

通過自定義類同時返回高度和平衡信息，代碼結構更清晰。

class BalanceInfo {
    boolean isBalanced;
    int height;
    
    BalanceInfo(boolean isBalanced, int height) {
        this.isBalanced = isBalanced;
        this.height = height;
    }
}

public class Solution {

    public boolean isBalanced(TreeNode root) {
        return checkBalance(root).isBalanced;
    }
    
    private BalanceInfo checkBalance(TreeNode node) {
        if (node == null) {
            return new BalanceInfo(true, 0); // 空節點平衡且高度為0
        }
        
        // 遞歸檢查左右子樹
        BalanceInfo leftInfo = checkBalance(node.left);
        BalanceInfo rightInfo = checkBalance(node.right);
        
        // 如果子樹不平衡，直接返回
        if (!leftInfo.isBalanced || !rightInfo.isBalanced) {
            return new BalanceInfo(false, -1); // 高度值此時不重要
        }
        
        // 檢查當前節點是否平衡
        if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
            return new BalanceInfo(false, -1);
        }
        
        // 返回當前節點的平衡信息和高高度
        int currentHeight = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new BalanceInfo(true, currentHeight);
    }
}