Обход Морриса приводит к исключению в LeetCode: очиститель адресов, переполнение стека
Я реализовал обход Морриса для решения проблемы LeetCode 98. Проверка двоичного дерева поиска:
Учитывая
rootдвоичного дерева, определите, является ли оно допустимым двоичным деревом поиска (BST).
Мой код
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
long aa = LONG_MIN;
long bb = LONG_MIN;
TreeNode* cur = root;
while(cur){
if (cur->left == NULL){
aa = max(aa, bb);
bb = cur->val;
if (aa != LONG_MIN && aa >= bb) return false;
cur = cur->right;
}
else{
TreeNode* prev = cur->left;
while(prev->right && prev->right != cur){
prev = prev->right;
}
if (prev->right == NULL){
prev->right = cur;
cur = cur->left;
}
else{
prev->right = NULL;
aa = max(aa, bb);
bb = cur->val;
if (aa != LONG_MIN && aa >= bb) return false;
cur = cur->right;
}
}
}
return true;
}
};
Это стандартная реализация обхода Морриса, где я только что добавил проверку (в двух местах кода), сравнивающую значение узла со значением его неупорядоченного предшественника, чтобы увидеть, является ли дерево действительным BST:
if (aa != LONG_MIN && aa >= bb) return false;
Ошибка:
Отправка этого кода в LeetCode приводит к следующей ошибке:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==22==ERROR: AddressSanitizer: stack-overflow on address 0x7ffcecdecff8 (pc 0x5627c311bad9 bp 0x7ffcecded010 sp 0x7ffcecded000 T0)
#0 0x5627c311bad9 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cad9)
#1 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
#2 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
#3 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
[...]
#243 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
#244 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
#245 0x5627c311bb00 in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cb00)
#246 0x5627c311badd in __TreeNodeUtils__::freeTreeHelper(TreeNode*) (solution+0x18cadd)
SUMMARY: AddressSanitizer: stack-overflow (solution+0x18cad9) in __TreeNodeUtils__::freeTreeHelper(TreeNode*)
==22==ABORTING
И если я удалю строку, проверяющую свойство BST:
if (aa != LONG_MIN && aa >= bb) return false;
...тогда ошибки больше нет. Почему эта строка выдает вышеуказанную ошибку?
Спасибо за ответ, я понимаю свою ошибку, обход Морриса исказил дерево, если я вернусь между ними.
Ответы 1
Ошибка возникает не в вашей функции, а в коде платформы LeetCode, который освобождает память, выделенную для дерева, после возврата вашей функции.
Обход Морриса изменяет дерево, временно вводя в него циклы. Это означает, что если вы прервете этот обход где-то на полпути, вы можете оставить дерево с теми циклами, которых не ожидает вызывающая сторона вашей функции. Когда этот вызывающий код пытается выполнить очистку (обратите внимание на упоминание freeTreeHelper в трассировке стека), он выполняется по этим циклам, предположительно с рекурсивной функцией, которая никогда не прекращает обход узлов в одном из этих циклов. В конечном итоге это приводит к переполнению стека.
Чтобы этого не произошло, убедитесь, что вы восстановили дерево в исходное состояние (или, по крайней мере, без циклов), прежде чем вернуться к вызывающему объекту.
Один из способов — продолжить обход Морриса до конца и просто отслеживать недопустимое состояние BST с помощью логической переменной.
Так:
class Solution {
public:
bool isValidBST(TreeNode* root) {
long aa = LONG_MIN;
long bb = LONG_MIN;
bool valid = true; // Add this boolean to keep track of BST validity.
TreeNode* cur = root;
while(cur){
if (cur->left == NULL){
aa = max(aa, bb);
bb = cur->val;
// Don't exit, but just keep track of the validity
valid &= aa == LONG_MIN || aa < bb;
cur = cur->right;
}
else{
TreeNode* prev = cur->left;
while(prev->right && prev->right != cur){
prev = prev->right;
}
if (prev->right == NULL){
prev->right = cur;
cur = cur->left;
}
else{
prev->right = NULL;
aa = max(aa, bb);
bb = cur->val;
// Don't exit, but just keep track of the validity
valid &= aa == LONG_MIN || aa < bb;
cur = cur->right;
}
}
}
return valid; // return the boolean we have kept updated
}
};
Спасибо большое, я понял свою ошибку. я застрял на этом на целый час.
Почему вы делаете
prev->right = cur;? Это нарушает дерево, и тестовый код не может очистить память. Вам вообще не следует изменять дерево. Не прикасайтесь к нему. Упростите этот код и попробуйте реализовать рекурсию примерно такbool testTree(TreeNode* root, int min, int max)