Java solution with O(n) time and O(1) space, using boolean trick to avoid unnecessary search


  • 0
    M
    public TreeNode first=null;
    public TreeNode second=null;
    public TreeNode prev=null;
    public void recoverTree(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(!inorder(list,root)){
            int temp=first.val;
            first.val=second.val;
            second.val=temp;
        }
        
        
    }
    public boolean inorder(List<Integer> list,TreeNode node){
        if(node==null){
            return false;
        }
        boolean found=false;
        found=found||inorder(list,node.left);
        if(list.size()==0 || node.val>=prev.val){
            list.add(node.val);
            prev=node;
        }
        else{
            if(first==null){
                first=prev;
                list.add(node.val);
                second=node;
                prev=node;
            }
            else{
                int temp=first.val;
                first.val=node.val;
                node.val=temp;
                found=true;
            }
        }
        found=found||inorder(list,node.right);
        return found;
        
        
        
    }

Log in to reply
 

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