恢复二叉搜索树。给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
大思路是求中序遍历，找逆序。一共有14种情况。如果是错误节点位置交换，题超难。如果是错误节点值交换，相对简单。实际上，错误节点位置交换才是正路，但leetcode没那么考。代码是错误节点值交换+莫里斯遍历。想看错误节点位置交换，请看文章末尾链接。
假设中序遍历结果是12345。14325两组降序。4和2交换。12435一组降序。4和3交换。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
head := &TreeNode{val: 2}
head.left = &TreeNode{val: 3}
head.right = &TreeNode{val: 1}
recoverTree(head)
fmt.Println(head.val)
fmt.Println(head.left.val)
fmt.Println(head.right.val)
}
// 不要提交这个类
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
// 如果能过leetcode，只需要提交这个方法即可
// 但其实recoverTree2才是正路，只不过leetcode没有那么考
func recoverTree(root *TreeNode) {
errors := twoErrors(root)
if errors[0] != nil && errors[1] != nil {
errors[0].val, errors[1].val = errors[1].val, errors[0].val
}
}
func twoErrors(head *TreeNode) []*TreeNode {
ans := make([]*TreeNode, 2)
if head == nil {
return ans
}
cur := head
var mostRight *TreeNode
var pre *TreeNode
var e1 *TreeNode
var e2 *TreeNode
for cur != nil {
mostRight = cur.left
if mostRight != nil {
for mostRight.right != nil && mostRight.right != cur {
mostRight = mostRight.right
}
if mostRight.right == nil {
mostRight.right = cur
cur = cur.left
continue
} else {
mostRight.right = nil
}
}
if pre != nil && pre.val >= cur.val {
if e1 == nil {
e1 = pre
}
e2 = cur
}
pre = cur
cur = cur.right
}
ans[0] = e1
ans[1] = e2
return ans
}执行结果如下：
