主題
題目連結：
題目意譯：
你被給定一個二元搜尋樹（Binary Search Tree，BST）的根節(jié)點 root，其中有恰好兩個節(jié)點的數(shù)值意外地被交換了。在不更動其結構的前提下，將樹復原回去。
限制：
樹中的節(jié)點數(shù)量位於範圍 [2, 1000] 中。
-2 ^ 31 ≦ Node.val ≦ 2 ^ 31 - 1
進階：一個使用 O(n) 空間的解法很直觀。那你可以推得一個 O(1) 空間的解法嗎？
範例測資：
範例 1：
輸入： root = [1,3,null,null,2]
輸出： [3,1,null,null,2]
解釋： 3 不能是 1 的左小孩，因為 3 > 1。將 1 和 3 交換便可以使此 BST 合法。
範例 2：
輸入： root = [3,1,4,null,null,2]
輸出： [2,1,4,null,null,3]
解釋： 2 不能在 3 的右子樹之中，因為 2 < 3。將 2 和 3 交換便可以使此 BST 合法。
解題思維：
以前有提及過 BST 的中序探訪（Inorder Traversal）是一個排序的數(shù)列見如這題），所以 O(n) 空間的解法就是把中序探訪的結果存起來看哪兩個數(shù)字的順序不對，將兩者對應的節(jié)點交換即可。
而 O(1) 就是需要使用 Morris Traversal（如這題），來在 O(1) 空間完成中序探訪，然後剩下跟 O(n) 解法很類似。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
