Runtime error, Last executed input: [2,1], 1


  • 0
    L

    I'm using Morris traversal algorithm to solve this problem, but I came across this error.

    Can anyone help me on this?

    /* Modification of Morris in-order tree traversal */
    int kthSmallest(struct TreeNode* root, int k) {
        if (root == NULL || k == 0) return -1;
    
        struct TreeNode *cur = root;
        struct TreeNode **p = NULL;
        int i = 0;
    
        while (cur != NULL) {
            if (cur->left != NULL) {
                /* find predecessor node */
                p = &(cur->left);
                while (1) {
                    if (*p == NULL) {
                        *p = cur;
                        cur = cur->left;
                        break;
                    }
    
                    if (*p == cur) {
                        if (++i == k) return cur->val;
                        *p = NULL;
                        cur = cur->right;
                        break;
                    }
                    p = &((*p)->right);
                }
            }
            else {
                if (++i == k) return cur->val;
                cur = cur->right;
            }
        }
    
        return -1; /* found nothing */
    }
    

    I get it. I just returned and did't recover some nodes of the tree. So maybe it causes access violation.

    This link is the right answer:
    https://leetcode.com/discuss/43299/o-k-space-o-n-time-10-short-lines-3-solutions

    But the time complexity will change from O(k) to O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.