99. 恢复二叉搜索树 难

99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？莫里斯，难

思路一

时间复杂度O(n)，n是节点个数，空间复杂度O(H)，递归栈的深度

中序遍历BST，依次访问的节点值是递增的，错误的BST会破坏递增性，从而能定位出错误。
我发现，错误有两种：

• 错误1：出现了两对不满足前小后大，需要交换第一对的第一个元素与第二对的第二个元素。
• 错误2：只出现一对不满足前小后大，交换这一对元素即可。

可以在的递归遍历过程中，将节点值推入一个数组，再遍历数组找出错误对。
但其实没必要。
只用比较前后访问的节点值，prev 保存上一个访问的节点，当前访问的是 root 节点。
每访问一个节点，如果prev.val>=root.val，就找到了一对“错误对”。
检查一下它是第一对错误对，还是第二对错误对。
遍历结束，就确定了待交换的两个错误点，进行交换。

func recoverTree(root *TreeNode) {
    pre := &TreeNode{Val : math.MinInt32 - 1}
    var err1 , err2 *TreeNode       //1,两种错误情况
    var inorder func(root *TreeNode)
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inorder(root.Left)
        if pre.Val >= root.Val && err1 == nil {
            err1 = pre
        }
        if pre.Val >= root.Val && err1 != nil {
            err2 = root
        }
        pre = root
        inorder(root.Right)
    }
    inorder(root)
    err1.Val, err2.Val = err2.Val, err1.Val
}

//中序递归，时空On
var last,first, second *TreeNode

func recoverTree(root *TreeNode) {
    last, first, second = nil, nil, nil
    dfs(root)
    first.Val, second.Val = second.Val, first.Val
}

func dfs(root *TreeNode) {
    if root == nil {
        return
    }
    dfs(root.Left)
    if last != nil && root.Val <= last.Val {
        if first != nil {
            second = root
            return //剪枝
        }
        first, second = last, root
    }
    last = root
    dfs(root.Right)
}

//莫里斯，时间On，空间O1，无敌！
func recoverTree(root *TreeNode) {
    var last, first, second, max *TreeNode
    for root != nil {
        if root.Left == nil {
            if last != nil && root.Val <= last.Val {
                if first == nil {
                    first = last
                }
                second = root
            }
            last = root
            root = root.Right
        } else {
            //寻找左树最大节点
            max = root.Left
            for max.Right != nil && max.Right != root {
                max = max.Right
            }

            if max.Right != root {
                // 未连接,连接到root
                max.Right = root
                root = root.Left
            } else {
                // 已连接，断开连接
                max.Right = nil
                if last != nil && root.Val <= last.Val {
                    if first == nil {
                        first = last
                    }
                    second = root
                }
                last = root
                root = root.Right
            }
        }
    }
    first.Val, second.Val = second.Val, first.Val
}