Morris 遍历导致 LeetCode 异常：地址清理、堆栈溢出

Question

我实现了 Morris 遍历来解决 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;
    }
};

这是一个标准的 [Morris 遍历实现]，我刚刚添加了一个检查（在代码中的两个位置），将节点的值与其中序前驱的值进行比较，以查看该树是否是有效的 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;

...然后就不再有错误了。为什么这一行会出现上述错误？

Answer 1

该错误不会发生在您的函数中，而是发生在 LeetCode 平台代码中，该代码在函数返回后释放分配给树的内存。

莫里斯遍历会改变树，暂时在其中引入循环。这意味着，如果您在中途的某个地方中止该遍历，则可能会在树中留下这些循环，这是函数的调用者不希望发生的情况。当该调用代码尝试清理时（请注意堆栈跟踪中提到的

freeTreeHelper

），它会沿着这些循环运行，大概使用递归函数，该函数永远不会停止遍历其中一个循环上的节点。这最终会导致堆栈溢出。

为了避免这种情况发生，请确保在返回调用者之前将树恢复到其原始状态（或至少没有循环）。

一种方法是继续 Morris 遍历到底，并使用布尔变量跟踪无效的 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
    }
};