题目

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2
Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

题解

第一版本

这一个版本超出内存限制了

func recoverTree(root *TreeNode)  {
    if root != nil {
        dfs(root)
    }
    
}

func dfs(root *TreeNode) bool{
    
    // bfs to move nextNode, swap with firstNode(root) and check
    // if succeed, return true and skip
    if root == nil {
        return false;
    }
    var queue []*TreeNode
    queue = append(queue, root)

    

    for len(queue) != 0 {
        
        headNode := queue[0]
        if headNode.Left != nil {queue =  append(queue, headNode.Left) }
        if headNode.Right != nil {queue =  append(queue, headNode.Right)}
        
        headNode.Left, headNode.Right = headNode.Right, headNode.Left
        if check(root) {
            return true
        }
        headNode.Left, headNode.Right = headNode.Right, headNode.Left
    }
    
    // firstNode move to next, pre-order dfs
    var flag bool
    if root.Left != nil{
        flag = dfs(root.Left)
    }
    
    if !flag && root.Right != nil{
        flag = dfs(root.Right)
    }
    
    return flag
} 


func check(root *TreeNode) bool{
    if root == nil {
        return true
    }
    
    checkLeft := (root.Left == nil || root.Left.Val < root.Val) && check(root.Left)
    checkRight := (root.Right == nil || root.Right.Val > root.Val) && check(root.Right)
    
    return (checkLeft && checkRight);
}

第二版本

“冒泡”思路。

func recoverTree2(root *TreeNode)  {
    help(root)
    first.Val, second.Val = second.Val, first.Val
}

func help(root *TreeNode) {
    if root == nil { return }
    help(root.Left)
    if(first == nil && prev.Val >= root.Val){
        first = prev
    }
    if(first != nil && prev.Val >= root.Val){
        second = root
    }
    prev = root
    help(root.Right)
}

令人诧异的是：同一份TestCase在Run和Submit居然有不同的结果！这属于编译器本地错误了，不管它

第三版本

要利用好Go的语言特性，使用channel 进行并发；且仅占O(1)内存空间

func Swap(x, y *TreeNode) {
    x.Val, y.Val = y.Val, x.Val
}

func Inorder(c chan *TreeNode, root *TreeNode) {
    if root == nil {
        return
    }
    Inorder(c, root.Left)
    c <- root
    Inorder(c, root.Right)
}

func recoverTree(root *TreeNode) {
    c := make(chan *TreeNode)
    go func() {
        Inorder(c, root)
        close(c)
    }()

    var first, second *TreeNode
    prev := <-c
    for x := range c {
        if x.Val < prev.Val {
            if first == nil {
                first = prev
            } 
            if first != nil {
                second = x
            }
        }
        prev = x
    }
    Swap(first, second)
}