// public class TreeNode {
//     int val = 0;
//     TreeNode left = null;
//     TreeNode right = null;
// }

// 1. 先求出中序遍历，然后根据中序遍历的结果求出异常值
import java.util.*;
/**
解题思路：
1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，
   现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数

2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面
   所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
*/
public class Solution {
    List<Integer> list = new ArrayList();
    public int[] findError (TreeNode root) {
        int[] result = new int[2];
        if(root == null) {
            return result;
        }
        findErrorHelper(root);
        int i, j;
        for(i = 0; i < list.size() - 1; i++) {
            if(list.get(i) > list.get(i + 1)) {
                result[1] = list.get(i);
                break;
            }
        }
        for(j = list.size() - 1; j > i; j--) {
            if(list.get(j) < list.get(j - 1)) {
                result[0] = list.get(j);
                break;
            }
        }
        return result;
    }

    private void findErrorHelper(TreeNode root) {
        if(root != null) {
            findErrorHelper(root.left);
            list.add(root.val);
            findErrorHelper(root.right);
        }
    }
}



// 2. 直接在递归的过程中求出异常值
import java.util.*;
/**
解题思路：
    因为二叉搜索树的中序遍历是正序数组，所以直接进行中序遍历，遍历的过程中直接找出异常值
    分析结果可得，必然是一个较大的异常值交换到了前面，较小的异常值数放到了后面，
    所以遍历的过程中出现的第一个当前值小于前一个值的情况时，前一个值即为要找的较大的异常值，
    而出现的最后一个 当前值小于前一个值的情况时，当前值才是我们要找的较小的异常值，
    所以在遍历过程中需要覆盖前面所求的较小值。
*/
public class Solution {
    int[] result = new int[2];
    int index = 1;
    TreeNode preNode;
    public int[] findError (TreeNode root) {
        if(root == null) {
            return result;
        }
        findError(root.left);
        if(preNode == null) {
            preNode = root;
        }
        if(index == 1 && root.val < preNode.val) {
            result[index] = preNode.val;
            index--;
        }
        if(index == 0 && root.val < preNode.val) {
            result[index] = root.val;
        }
        preNode = root;
        findError(root.right);
        return result;
    }
}