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 {
	public void recoverTree(TreeNode root) {
        List<Integer> list = new ArrayList(); // 存放中序遍历的列表
        inOrder(root, list); 
        int[] arr = new int[2]; // 存放错误的两个节点
        findErr(list, arr); 
        solve(root, arr[0], arr[1], 0);
	}
    // 中序遍历填充list
    static void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
    // 找到顺序错误的两个节点
    static void findErr(List<Integer> list, int[] arr) {
        int index1 = -1, index2 = -1; // 存放两个错误节点的索引
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) { // 判断前后顺序
                if (index1 == -1) index1 = i;
                else {
                    index2 = i + 1;
                    break; // 第二个也找到了提前结束
                }
            }
        }
        if (index2 == -1) index2 = index1 + 1; // 两个错误节点相邻时
        arr[0] = list.get(index1);
        arr[1] = list.get(index2);
    }
    // 恢复二叉搜索树
    static void solve(TreeNode root, int err1, int err2, int times) {
        if (times >= 2 || root == null) return; // 操作次数达2次恢复完成
        // 互换两个节点
        if (root.val == err1 || root.val == err2) {
            if (root.val == err1) root.val = err2;
            else root.val = err1;
            times++;
        }
        solve(root.left, err1, err2, times);
        solve(root.right, err1, err2, times);
    }
}

① 中序遍历的二叉搜索树得到的数组顺序应是从小到大排列的，所以找到错误的两个节点(非相邻)，互换这两个节点即可复原。

1 2 3 4 5 6 -> 1 5 3 4 2 6

② 另一种情况是错误的两个节点是相邻的，那么要注意遍历互换相邻两个即可。

1 2 3 4 5 6 -> 1 2 4 3 5 6