Got TLE for {2,3,1}, but it takes 0ms in eclipse


  • 0
    M

    Hi all, I'm getting problem with the code below, please take a look at it if you've got time.
    I used Morris inorder traversal to find the wrong nodes and switch them, but got stuck at the test case{2,3,1}. I tested it on my eclipse, and it cost 0ms for this case, so what's wrong here?
    Thank you!

    public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode mis1 = null;
        TreeNode mis2 = null;
        TreeNode prev = null;
        TreeNode tmp=root;
        
        while(cur!=null){
            if(cur.left==null){
                if(prev!=null){
                    if(prev.val>cur.val){
                        if(mis1==null) {mis1=prev;mis2=cur;}
                        else {mis2=cur;break;}
                    }
                }
                prev=cur;
                cur=cur.right;
            }
            else{
                tmp=cur.left;
                while(tmp.right!=null&&tmp.right!=cur) tmp=tmp.right;
                if(tmp.right==null){
                    tmp.right=cur;
                    cur=cur.left;
                }
                else{
                    if(prev!=null){
                        if(prev.val>cur.val){
                            if(mis1==null) {mis1=prev;mis2=cur;}
                            else {mis2=cur;break;}
                        }
                    }
                    tmp.right=null;
                    prev=cur;
                    cur=cur.right;
                }
            }
        }
        int tmpval = mis2.val;
        mis2.val=mis1.val;
        mis1.val=tmpval;
    }
    

    }


  • 6
    N

    Morris inorder traversal modifies the original BST structure.
    It's your duty to restore the structure.

    TLE comes from OJ checking.

    Just remove all "BREAK"; let the while loop finish the job before swapping values.


  • 0
    J

    this is my answer:

    You only need find the two element. and swap the value.

     TreeNode *last =NULL, *first = NULL, *second = NULL;
        
        void reco(TreeNode *node) {
            if (!node) return ;
            
            reco(node->left);
            
            if (last) {
              if (!first) {
                  if (last->val > node->val) {
                      first = last;
                      second = node;
                  }
              }else {
                  if (last->val > node->val) {
                      second = node;
                  }
              }
                
            }
            
            last = node;
            reco(node->right);
        }
    
    
     void recoverTree(TreeNode *root) {
            if (!root) return;
            
            reco(root);
           
           if (first && second) {
                first->val = first->val ^ second->val;
                second->val = first->val ^ second->val;
                first->val = first->val ^ second->val;
           }
           
        }

Log in to reply
 

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