99. 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.

DFS中序搜索，额外记录访问的前一个节点。
如果当前节点与前一个节点的顺序不对，则暂且认为先后两个节点的位置均不正确。
（前一个大于后一个的值，由于是第一个不满足递增条件的位置，因此前一个的位置一定是错误的。但此时当前值不一定是错误的。）
继续递归，如果发现新的节点位置不正确，则后一个节点位置正确，更新当前节点为不正确的节点。
（由于是第二个不满足递增条件的位置，因此当前值是错误的。）
交换两个位置不正确的节点的值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode prev;
    boolean flag;
    TreeNode[] wrong;
    public void recoverTree(TreeNode root) {
        wrong = new TreeNode[2];
        prev = new TreeNode(Integer.MIN_VALUE);
        flag = true;
        
        dfs(root);
        
        int swap = wrong[0].val;
        wrong[0].val = wrong[1].val;
        wrong[1].val = swap;
        
        
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(prev.val > root.val){
            if(flag){
                wrong[0] = prev;
                flag = false;
            }
            wrong[1] = root;
        }
        prev = root;
        dfs(root.right);
    }
}