恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1

  /

 3

  \

   2

输出: [3,1,null,null,2]

   3

  /

 1

  \

   2

示例 2:

输入: [3,1,4,null,null,2]

  3

 / \

1   4

   /

  2

输出: [2,1,4,null,null,3]

  2

 / \

1   4

   /

  3

进阶:

使用 O(n) 空间复杂度的解法很容易实现。

中序遍历 二分查找树

们判断是否是一个合法的二分查找树是使用到了中序遍历。原因就是二分查找树的一个性质，左孩子小于根节点，根节点小于右孩子。所以做一次中序遍历，产生的序列就是从小到大排列的有序序列。

回到这道题，题目交换了两个数字，其实就是在有序序列中交换了两个数字。而我们只需要把它还原。

交换的位置的话就是两种情况。

相邻的两个数字交换

[ 1 2 3 4 5 ] 中 2 和 3 进行交换，[ 1 3 2 4 5 ]，这样的话只产生一组逆序的数字（正常情况是从小到大排序，交换后产生了从大到小），3 2。

我们只需要遍历数组，找到后，把这一组的两个数字进行交换即可。

不相邻的两个数字交换

[ 1 2 3 4 5 ] 中 2 和 5 进行交换，[ 1 5 3 4 2 ]，这样的话其实就是产生了两组逆序的数字对。5 3 和 4 2。

所以我们只需要遍历数组，然后找到这两组逆序对，然后把第一组前一个数字和第二组后一个数字进行交换即完成了还原。

所以在中序遍历中，只需要利用一个 pre 节点和当前节点比较，如果 pre 节点的值大于当前节点的值，那么就是我们要找的逆序的数字。分别用两个指针 first 和 second 保存即可。如果找到第二组逆序的数字，我们就把 second 更新为当前节点。最后把 first 和 second 两个的数字交换即可。

主函数

public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    TreeNode node1 = new TreeNode(5);
    TreeNode node2 = new TreeNode(3);
    TreeNode node3 = new TreeNode(4);
    TreeNode node4 = new TreeNode(2);
    root.left=node1;
    root.right=node2;
    node2.left=node3;
    node2.right=node4;
    recoverTree(root);
}

中序遍历

static TreeNode first = null;
static TreeNode second = null;
public static void recoverTree(TreeNode root) {
    inorderTraversal(root);
    //在这里已经找到了，所以进行交换
    int temp = first.val;
    first.val = second.val;
    second.val = temp;
}
static TreeNode pre = null;
private static void inorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left);
    /*******************************************************/
    if(pre == null){
        pre = root;
    }
    else {
        //第一次遇到逆序对
        if(root.val < pre.val){
            if(first==null){
                first = pre;
                second = root;
            }else {
                //第二次遇到逆序对
                second = root;
            }
        }
    }

方法2

1.通过中序遍历，将遍历结果放在一个ArrayList中；

2.双指针，从头尾向中间靠；

import java.util.ArrayList;

public class Solution099 {

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public void recoverTree(TreeNode root) {
        ArrayList<TreeNode> path = new ArrayList<TreeNode>();
        //中序遍历，获得这个二叉搜索树的遍历序列
        dfs(root, path);

        int start = 0, end = path.size() - 1;
        while (start < end) {   //注意是<
            if (path.get(start).val < path.get(start + 1).val) {
                start++;
            } else if (path.get(end).val > path.get(end - 1).val) {
                end--;
            } else {
                //找到错误的节点，交换回来，只交换val
                int tmp = path.get(end).val;
                path.get(end).val = path.get(start).val;
                path.get(start).val = tmp;
                return;
            }
        }

    }

    //中序遍历，获得这个二叉搜索树的遍历序列
    private void dfs(TreeNode node, ArrayList<TreeNode> path) {
        if (node == null) {
            return;
        }
        dfs(node.left, path);
        path.add(node);        //将该节点加入path
        dfs(node.right,path);
    }
}