C code here ... 9 ms... Time O(n) and Space O(1).


  • 0
    O

    /* Using Morris Inorder traversal. Time O(n) and Space O(1). Execution time was 9 ms. You can make it O(k) Time by uncomment "break" in the code. However, for some reason, lee code compiler give run time error !! !*/

    int kthSmallest(struct TreeNode* root, int k) {

    struct TreeNode* current, * pre;
    int rv = 0;
    current = root;
    while ( current != 0 )
        {
            if ( current->left == 0 )
                {
                    if (!(--k))
                        {
                            rv= current->val;
                            //break;
                        }
                    current = current->right;
                }
            else
            {
                pre = current->left;
                while ( pre->right != 0 && pre->right != current)
                    pre = pre->right;
                if ( pre->right == 0)
                {
                    pre->right = current;
                    current = current->left;
                }
                else
                {
                    if (!(--k))
                        {
                            rv= current->val;
                            //break;
                        }
                    pre->right = 0;
                    current = current->right;
                }
            }
        }
    

    return (rv);
    }


Log in to reply
 

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