1. 題目描寫

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

2. 題目分析

題目的大意是，在2叉排序樹中有兩個節點被交換了，要求把樹恢復成2叉排序樹。

1個最簡單的辦法是，中序遍歷2叉樹生成序列，然后對序列中排序毛病的進行調劑。最后再進行1次賦值操作。這類方法的空間復雜度為O(n)。

但是，題目中要求空間復雜度為常數，所以需要換1種方法。

遞歸中序遍歷2叉樹，設置1個prev指針，記錄當前節點中序遍用時的前節點，如果當前節點大于prev節點的值，說明需要調劑次序。

3. 示例代碼

4. 小結

有1個技能是，若遍歷全部序列進程中只出現了1次次序毛病，說明就是這兩個相鄰節點需要被交換。如果出現了兩次次序毛病，那就需要交換這兩個節點。