题目

给定一个二叉搜索树的根 root，这个二叉树恰好两个节点被错误的交换了，在不改变树结构的情况下，恢复这个二叉搜索树。

解析

对于二叉搜索树来说，中续遍历是单调递增的，如果出现节点错位的情况，那么当我们遍历到一个出错的节点时，会发现这个节点小于前一个节点，此时，我们就找到了一个出错的节点，然后，我们继续遍历这个树，发现另一个同样情况的节点，此时我们交换这两个节点即可。
问题就是，在两次寻找中，我们应该交换哪两个节点。
对于一次中序遍历来说，存在两种情况

（3,1,2）
（3,2,1）
即，需要交换的节点可能是第一次出错的两个节点，也可能是第一次出错的前一个节点和第二次出错的节点。
即

if first == nil
      fist = vis
      second = node
if first != nil
    second = node

最后，我们交换 1, 2,节点即可。

伪代码

for{
  if node == nil && stack != nil
      node = stack.push()
      if pre = node.Left && visit.val > node.val
            if first == nil
                first = node
                second = visit
            else
                second = node
      if pre == node.right
         pre = node
         node = nil
      else
        stack.push(node)
        node = node.Right
        continue
  stack.push(node)
  node = node.left
}

代码

func recoverTree(root *TreeNode)  {
    stack := make([]*TreeNode, 64)
    i:=0
    var vis, pre, first, second *TreeNode
    node := root
    for {
        if node == nil && i == 0 {
            break
        }
        if node == nil {
            node = stack[i-1]
            i--
            if pre == node.Left {
                if vis != nil && vis.Val > node.Val {
                    if first == nil {
                        first = vis
                        second = node
                    }else {
                        second = node
                        break
                    }
                }
                vis = node
            }
            if pre == node.Right {
                pre = node
                node = nil
                continue
            }else {
                pre = nil
                i++
                node = node.Right
                continue
            }
        }
        stack[i] = node
        i++
        node = node.Left
    }
    first.Val, second.Val = second.Val, first.Val
}