Day. 28 Recover Binary Search Tree

Leetcode #99. Recover Binary Search Tree

简单来说二元树里面，有两个node的值位置是错的，请把它纠正回来
像例子1，3在1的左边，不合二元树的特性，所以1跟3交换，这样就符合二元树的特性。

防雷
防雷
防雷

大家还记得InOrder的走访吗？
它会照着值的顺序，我们只要找到不照顺序的值，把它记下来，最後做交换就可以解决了

例1

     2
    / \
   3   1

firstNode, secondNode用来记需要交换的两个node
以InOrder的顺序output: [3,2,1]
正确的二元树每一个值都会比前面的小，当2发现前面的是3比自己大，我们把3记在firstNode，2记在secondNode，到1的位置发现2比较大，firstNode的位置已经有了，所以一样放在secondNode。
最後3跟1交换

例2

      3
    /   \
   1     4
        /
       2

以InOrder的顺序output: [1,3,2,4]
2比3小，firstNode=3，secondNode=2，最後交换。

程序

func recoverTree(root *TreeNode) {
	var firstNode, secondNode, preNode *TreeNode
	InOrderDFS(root, &preNode, &firstNode, &secondNode)

	firstNode.Val, secondNode.Val = secondNode.Val, firstNode.Val
}

func InOrderDFS(node *TreeNode, preNode, firstNode, secondNode **TreeNode) {
	if node == nil {
		return
	}

	InOrderDFS(node.Left, preNode, firstNode, secondNode)

	if *preNode != nil && node.Val < (*preNode).Val {
		if *firstNode == nil {
			*firstNode = *preNode
		}
		*secondNode = node
	}

    // 这一行很重要 前一个节点要用InOrder的顺序
	*preNode = node

	InOrderDFS(node.Right, preNode, firstNode, secondNode)
}