Why RE ? Morris traversal based solution


  • 0

    For the below test case, it will cause RE ! But it output 1 and 2.....So what happened when it return ???

    [1,2]
    1
    

    Here is my implementation

    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            TreeNode *pre, *cur;
            int count=k, result=0;
            cur=root;
            while(cur){
                if(cur->left){
                    pre=cur->left;
                    while(pre->right && pre->right!=cur)  pre=pre->right;
                    if(!pre->right)  { 
                        pre->right=cur; 
                        cur=cur->left; 
                    }
                    else  { 
                        pre->right=NULL; 
                        count--; 
                        if(count==0) {
                            result=cur->val;
                            return result;
                        }
                        cur=cur->right; 
                    }
                }
                else{
                    count--;
                    cout<<"1"<<endl;
                    if(count==0) {
                        result=cur->val;
                        cout<<"2"<<endl;
                        return result;
                    }
                    cur=cur->right;
                }
            }
            
            return -1;
        }
    };

  • 0
    M

    Morris traversal modify tree structure during the run, if you run over the entire tree the structure will be recovered. However if you return from the middle, the tree structure is likely to be modified


  • 0

    I know you mean, You mean that I get the right result but with the tree structure not recovered fully ??

    Do I get what you mean ?

    Thanks anyway .^..^.


Log in to reply
 

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