99. Recover Binary Search Tree!

class Solution {
    TreeNode first = null;
    TreeNode second = null;

    TreeNode prev = null;
    
    public void recoverTree(TreeNode root) {
        // The first element is always larger than its next one, while the second element is always smaller than its previous one.
        // The recursive call will use a O(logN) space.
        inorder(root);
        int temp = first.val;
        first.val=second.val;
        second.val = temp;
    }
    
    private void inorder(TreeNode node){
        if(node==null) return;
        
        inorder(node.left);
        if(prev!=null && prev.val>=node.val){
            if (first == null){
                first = prev;
            }
            second = node;
        }
        prev = node;
        inorder(node.right);
    }
}