проверьте дерево сбалансировано, почему мой код не работает?
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, если дерево не сбалансировано, но когда я запускаю его, оно не может правильно проверить, сбалансировано дерево или нет, кто-нибудь может мне помочь? Спасибо
Решение
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))
}
также вы можете проверить переполнение стека Сначала это может помочь.
Другие решения
Наконец, я нашел, что могу это исправить и сделать это 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;
}