99.恢复二叉搜索树——hard

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。

示例 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) 空间复杂度的解法很容易实现。
• 你能想出一个只使用常数空间的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree

思路：
正常思路是使用中序遍历
解法一：中序遍历结果为一个升序数组，错误交换的节点必然有a解法二：增加一个辅助的pre指针，记录 上一个 节点的值。如果 当前节点的值，小于 上一个节点的值，这就找到了需要交换的节点：空间复杂度O(h) h是二叉搜索数高度。
解法三：常数空间的解决方案必然是mirrors遍历。
复杂度分析：
时间复杂度O(n) 实际因为需要对每个节点遍历两次为O(2n)
空间复杂度O(1)

var recoverTree = function (root) {
    const swap = (a, b) => {
        [a.val, b.val] = [b.val, a.val];
    };
    const mirrors = (root) => {
        let x = null, y = null, pre = null, pred = null;
        while (root) {
            if (root.left) {
                pre = root.left;
                while (pre.right && pre.right !== root) {
                    pre = pre.right;
                }
                if (!pre.right) {
                    pre.right = root;
                    root = root.left;
                } else {
                    if (pred !== null && pred.val > root.val) {
                        y = root;
                        if (x === null) {
                            x = pred;
                        }
                    }
                    pred = root;
                    pre.right = null;
                    root = root.right;
                }
            } else {
                if (pred !== null && pred.val > root.val) {
                    y = root;
                    if (x === null) {
                        x = pred;
                    }
                }
                pred = root;
                root = root.right;
            }
        }
        swap(x, y);
    };
    mirrors(root);
    return root;
};