C# solution O(logN*logN) time O(1)space


  • 0
    Y

    The basic idea is find the previous and next node of a specific node in in-order traversal. If we know the previous node and posterior node of a node, then we can judge this node is the wrong node or not.

    public class Solution {
    TreeNode big=null,small=null;
    public void RecoverTree(TreeNode root) {
        if(root==null)
        return;
        find(root,null,null);
        int tmp=big.val;
        big.val=small.val;
        small.val=tmp;
        return;
    }
    int find(TreeNode root,object pre,object post){
    
        int front,back;
        if(root.left==null){
            if(pre==null)
            front=root.val-1;
            else
        front=(int)pre;
        }else{
            front=find(root.left,pre,root.val);
        }
        if(root.right==null)
        {
            if(post==null)
            back=root.val+1;
            else
            back=(int)post;
        }else{
            back=findleft(root.right);
        }
        if(front<root.val&&root.val>back&&big==null)
        big=root;
        if(front>root.val&&root.val<back)
        small=root;
        if(root.right!=null)
        return find(root.right,root.val,post);
        else
        return root.val;
     
    }
    int findleft(TreeNode root){
        if(root.left!=null)
        return findleft(root.left);
        return root.val;
    }
    

    }


  • 0

    It's not constant space because it's recursive and recursion uses stack space.


Log in to reply
 

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