0099.恢复二叉搜索树

https://leetcode.cn/problems/recover-binary-search-tree/

方法一：隐式中序遍历

时间复杂度 $O(N)$，空间复杂度 $O(H)$，其中 $N$ 为二叉搜索树的节点个数，$H$ 为二叉搜索树的高度。

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func recoverTree(root *TreeNode) {
	var pre *TreeNode = &TreeNode{Val: -1<<31 - 1}
	var first, last *TreeNode = nil, nil
	var middle func(n *TreeNode)
	middle = func(n *TreeNode) {
		if n == nil {
			return
		}
		middle(n.Left)
		if n.Val < pre.Val {
			last = n
			if first == nil {
				first = pre
			} else {
				return
			}
		}
		pre = n
		middle(n.Right)
	}
	middle(root)
	first.Val, last.Val = last.Val, first.Val
}