您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 110：平衡二叉樹判定 - 遞歸與優化解法

編輯：關於C++

問題描述

給定一棵二叉樹，判斷其是否為高度平衡。平衡二叉樹定義：任意節點的左右子樹高度差不超過 1。

遞歸解法（自頂向下）

分別遞歸計算左右子樹高度，再遞歸判斷左右子樹是否平衡。缺點：重複計算高度，時間複雜度 O(n²)。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        return abs(lh - rh) <= 1 
            && isBalanced(root->left) 
            && isBalanced(root->right);
    }
    
    int getHeight(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }
};

優化解法：自底向上（後序遍歷）

在計算高度的同時檢查平衡性，若發現不平衡直接返回 -1 作為標記，避免重複計算，時間複雜度 O(n)。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }
    
    int checkHeight(TreeNode* root) {
        if (!root) return 0;
        int left = checkHeight(root->left);
        if (left == -1) return -1;
        int right = checkHeight(root->right);
        if (right == -1) return -1;
        if (abs(left - right) > 1) return -1;
        return 1 + max(left, right);
    }
};