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)
}