# 99. Recover Binary Search Tree

###### tags: `leetcode`,`BST`,`medium`

>ref: https://leetcode.com/problems/recover-binary-search-tree/
>
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.




## first try: loop twice, time(O\(N\)) spatial(O(1))

>1. inorder traverse and store treenode in list
>2. loop list find the first case of prev.val>cur.val
big= prev and small=cur, then loop to end find prev.val>cur.val small= cur
>3. finally, swap value of big and small

    public void recoverTree(TreeNode root) {
        
        List<TreeNode> list= new LinkedList<>();
        traverse(root,list);
        
        TreeNode big= new TreeNode();
        TreeNode small=new TreeNode();
        
        int countbig=0;
        int countsmall=0;
        
        
        int i;
        for(i=1; i<list.size();i++){
                if(list.get(i).val<list.get(i-1).val ){
                     big=list.get(i-1);
                     small=list.get(i);
                    break;
                }
            }
        for(int j=i; j<list.size();j++){
                if(list.get(j).val<list.get(j-1).val ){
                     small=list.get(j);
                }
            }
        
        int cur= big.val;
        
        big.val=small.val;
        
        small.val=cur;
        
        return;
        }
    
    
    
    public void traverse(TreeNode root,List<TreeNode> list){
        
        if(root==null) return ;
        
        if(root.left!=null){
            traverse(root.left,list);
        }
        
        list.add(root);
        System.out.println(root.val);
        
        if(root.right!=null){
            traverse(root.right,list);
        }
        
    }

## concise traverse one time

>1. prev as cur
>2. f only find once , then s will loop to end, will occur once(f and s is connect) or twice(f and s is separated)
>3. interchange f and s value

    TreeNode f;
    TreeNode s;
    
    public void recoverTree(TreeNode root) {
        
        traverse(root);
        
        int cur=f.val;
        
        f.val=s.val;
        
        s.val=cur;

   }
    
    
    TreeNode prev=null;
    
    public void traverse(TreeNode root){

        if(root==null) return;
        
        traverse(root.left);
        
        
        if(prev==null){
            prev=root;
        }
        
        if(f==null && prev.val > root.val){
            f=prev;
        }
        
        if(prev.val >root.val){
            s=root;
        }
        
        prev=root;
        
        traverse(root.right);
    }