给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。提示：
- 树上节点的数目在范围 [2, 1000] 内
- -231 <= Node.val <= 231 – 1
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
解题：
// 没解出来。。。官方解答：
1.显式中序遍历
func recoverTree(root *TreeNode) {
var nums []int
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
nums = append(nums, node.Val)
inorder(node.Right)
}
inorder(root)
x, y := findTwoSwapped(nums)
recoverNode(root, 2, x, y)
}
func findTwoSwapped(nums []int) (int, int) {
index1, index2 := -1, -1
for i := 0; i < len(nums)-1; i++ {
if nums[i+1] < nums[i] {
index2 = i + 1
if index1 == -1 {
index1 = i
} else {
break
}
}
}
x, y := nums[index1], nums[index2]
return x, y
}
func recoverNode(root *TreeNode, count, x, y int) {
if root == nil {
return
}
if root.Val == x || root.Val == y {
if root.Val == x {
root.Val = y
} else {
root.Val = x
}
count--
if count == 0 {
return
}
}
recoverNode(root.Right, count, x, y)
recoverNode(root.Left, count, x, y)
}2.隐式中序遍历
func recoverTree(root *TreeNode) {
var stack []*TreeNode
var x, y, pred *TreeNode
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if pred != nil && root.Val < pred.Val {
y = root
if x == nil {
x = pred
} else {
break
}
}
pred = root
root = root.Right
}
x.Val, y.Val = y.Val, x.Val
}3.Morris 中序遍历
func recoverTree(root *TreeNode) {
var x, y, pred, predecessor *TreeNode
for root != nil {
if root.Left != nil {
// predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
predecessor = root.Left
for predecessor.Right != nil && predecessor.Right != root {
predecessor = predecessor.Right
}
// 让 predecessor 的右指针指向 root，继续遍历左子树
if predecessor.Right == nil {
predecessor.Right = root
root = root.Left
} else { // 说明左子树已经访问完了，我们需要断开链接
if pred != nil && root.Val < pred.Val {
y = root
if x == nil {
x = pred
}
}
pred = root
predecessor.Right = nil
root = root.Right
}
} else { // 如果没有左孩子，则直接访问右孩子
if pred != nil && root.Val < pred.Val {
y = root
if x == nil {
x = pred
}
}
pred = root
root = root.Right
}
}
x.Val, y.Val = y.Val, x.Val
}