题目描述

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

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

你能想出一个只使用常数空间的解决方案吗？

样例

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

  3
 / \
1   4
   /
  2

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

  2
 / \
1   4
   /
  3

算法1

(Morris遍历) $O(n)$

* 核心思路就是遍历到每个点的前驱节点时，把前驱节点的右侧指针指向这个点，以达到类似于获取栈顶元素的作用。
* 寻找逆序对最后交换，有两种情况。
    第一种：1 2 4 3 5， 找到逆序对中的两个数即可
    第二种：1 6 3 4 5 2 7 8，找到两个逆序对，则需要找到第一个逆序对里的第一个数6和第二个逆序对里的第二个数2
* 两种情况
    1.没有左子树，直接遍历该点，然后走到右儿子
    2.有左子树，找前驱节点p
        (1).如果p.right为空，则p.right = root , root = root.left
        (2).如果p.right不为空，说明左子树遍历过了，p.right = null, 遍历当前节点，root = root.right
只有两处需要遍历当前节点，则在这两处更新上一个节点last，以及记录是否存在逆序对。

Java 代码

class Solution {
    public void recoverTree(TreeNode root) {
        if(root == null) return;
        TreeNode first = null, second = null, last = null;
        while(root != null){
            if(root.left == null){
                if(last != null && last.val > root.val){
                    if(first == null) {
                        first = last;
                        second = root;
                    }
                    else second = root;
                }
                last = root;
                root = root.right;
            }else{
                TreeNode p = root.left;
                while(p.right != null && p.right != root) p = p.right;
                if(p.right == null){
                    p.right = root;
                    root = root.left;
                }else{
                    p.right = null;
                    if(last != null && last.val > root.val){
                        if(first == null) {
                            first = last;
                            second = root;
                        }
                        else second = root;
                    }
                    last = root;
                    root = root.right;
                }
            }
        }
        swap(first,second);
    }

    void swap(TreeNode p, TreeNode q){
        int t = p.val;
        p.val = q.val;
        q.val = t;
    }
}