使用Morris遍历查找二叉搜索树第k小元素时遇栈溢出错误求助

尝试用Morris遍历查找二叉搜索树（BST）的第k小元素，但每次运行都触发Runtime error，无法定位问题。以下是代码及报错信息：

int kthSmallest(TreeNode* root, int k) {
        if(root == NULL) return -1;
        int ans = -1;
        TreeNode* curr = root;
        TreeNode* temp;
        while(curr != nullptr && k>0){
            if(curr -> left == nullptr){
                temp = curr;
                curr = curr -> right;
                k--;
            }
            else{
                TreeNode* pr = curr -> left;
                while(pr -> right != nullptr && pr -> right != curr){
                    pr = pr -> right;
                }
                if(pr -> right == nullptr){
                    pr -> right = curr;
                    curr = curr -> left;
                }
                else if(pr -> right == curr){
                    pr -> right = nullptr;
                    temp = curr;
                    curr = curr -> right;
                    k--;
                }
            }
        }
        return temp -> val;
    }

报错信息：

AddressSanitizer:DEADLYSIGNAL #

22
ERROR:
AddressSanitizer:
stack-overflow on address 0x7ffd97244ff8
(pc 0x00000037d5d9 bp 0x7ffd97245010 sp 0x7ffd97245000 T0)
22
ABORTING

核心错误原因 #

1. 循环条件运算符错误：若实际代码中误将逻辑与&&写成位与&，会导致循环条件始终为真，触发无限循环，不断在栈上创建局部变量（如TreeNode* pr），最终耗尽栈空间引发溢出。
2. 野指针访问：TreeNode* temp未初始化，若k的数值大于BST节点总数，循环结束后temp仍为野指针，访问temp->val会触发内存错误，甚至破坏栈结构。
3. 未提前终止循环：找到第k小元素后未及时退出，继续遍历可能引发不必要的指针操作。

修复后的代码 #

int kthSmallest(TreeNode* root, int k) {
    if (root == nullptr || k <= 0) return -1; // 提前拦截无效输入
    TreeNode* curr = root;
    TreeNode* temp = nullptr; // 初始化指针，避免野指针
    while (curr != nullptr && k > 0) {
        if (curr->left == nullptr) {
            temp = curr;
            k--;
            if (k == 0) break; // 找到目标后立即退出循环
            curr = curr->right;
        } else {
            TreeNode* pr = curr->left;
            // 查找左子树的最右前驱节点
            while (pr->right != nullptr && pr->right != curr) {
                pr = pr->right;
            }
            if (pr->right == nullptr) {
                // 建立线索，标记前驱节点
                pr->right = curr;
                curr = curr->left;
            } else {
                // 恢复树结构，访问当前节点
                pr->right = nullptr;
                temp = curr;
                k--;
                if (k == 0) break; // 找到目标后立即退出循环
                curr = curr->right;
            }
        }
    }
    // 判空后返回，避免野指针访问
    return temp != nullptr ? temp->val : -1;
}

关键修复点说明 #

• 确保循环条件使用逻辑与&&，保证curr为空或k减至0时能终止循环，避免无限栈消耗。
• 初始化temp为nullptr，返回前做判空处理，彻底解决野指针问题。
• 找到第k小元素后立即跳出循环，提升效率同时避免后续不必要的指针操作。

内容的提问来源于stack exchange，提问作者Aditya Prakash