c++ - 检查树是否平衡，为什么我的代码不起作用？

Question

bool isBalanced(){
    bool balance = true;
    isBalanced(root, balance);
    return balance;
}
int isBalanced(Node* root, bool& balance){
    if (root == NULL) return 0;
    int left_height = 1 + height(root->left);
    int right_height = 1 + height(root->right);
    if (std::abs(left_height - right_height) > 1){
        balance = false;
    }
    return left_height > right_height ? left_height : right_height;
}

如果树不平衡，我希望 isBalanced() 将平衡设置为 false，但是当我运行它时，它无法正确检查树是否平衡，有人可以帮助我吗？谢谢

Answer 1

bool isBalanced(Node *root)
{ 
   if(root == NULL)
         return true; 

   int left = height(root->left);
   int right= height(root->right);

   return abs(left - right) <= 1 && 
   isBalanced(root->left) &&
   isBalanced(root->right))
}

您也可以先检查stackoverflow，它可能会有所帮助。

Answer 2

最后，我发现我可以修复它并使其成为 O(n) 时间和 O(logN) 空间复杂度

bool isBalanced(){
    if (isBalanced(root) == -1){
        return false;
}
    return true;
}
int isBalanced(Node* root){
    if (root == NULL) return 0;
    int left_height = 1 + isBalanced(root->left);
    if (left_height == -1){
        return -1;
    }
    int right_height = 1 + isBalanced(root->right);
    if (right_height == -1){
        return -1;
    }
    if (std::abs(left_height - right_height) > 1){
        return -1;
    }
    return left_height > right_height ? left_height : right_height;
}