Medium
99. Recover Binary Search Tree
treedepth-first-searchbinary-search-treebinary-tree
解題說明
Recover Binary Search Tree
題目描述：給定一棵二元搜尋樹（BST），其中恰好有兩個節點的值被交換了，請在不改變樹結構的前提下恢復這棵樹。
解題思路：BST 的中序遍歷結果應為嚴格遞增序列。如果有兩個節點被交換，中序序列中會出現一或兩處「逆序對」（前一個值大於後一個值）。第一次逆序的前者和最後一次逆序的後者就是被交換的兩個節點。我們可以用 Morris Traversal 在 O(1) 額外空間下完成中序遍歷，同時記錄這兩個異常節點，最後交換它們的值即可。
C++ 解法
複雜度分析
時間複雜度：O(n) — Morris Traversal 每條邊最多被訪問兩次，整體為線性時間。
空間複雜度：O(1) — 僅使用常數個指標變數，不需要遞迴堆疊或額外資料結構。
虛擬碼
1. Initialize first = null, second = null, prev = null, cur = root
2. While cur is not null (Morris inorder traversal):
a. If cur has no left child:
- Visit cur: if prev exists and prev.val > cur.val, record anomaly
- Set prev = cur, move cur = cur.right
b. Else find inorder predecessor of cur:
- If predecessor's right is null: set it to cur, move cur = cur.left
- Else (predecessor's right == cur): restore it to null, visit cur, prev = cur, move cur = cur.right
3. When recording anomaly:
- First time: first = prev (the larger misplaced node)
- Every time: second = cur (the smaller misplaced node)
4. Swap first.val and second.val其他解法
遞迴中序遍歷 O(n) 空間：用標準遞迴中序遍歷，記錄 prev 指標找出兩個逆序節點。程式碼更簡潔但遞迴堆疊佔用 O(h) 空間（h 為樹高），最壞情況為 O(n)。
迭代堆疊中序遍歷 O(h) 空間：用顯式堆疊替代遞迴，同樣追蹤 prev 節點。空間複雜度為 O(h)，比 Morris Traversal 多一些空間但實作較直觀。
延伸思考
- 如果不允許交換節點值，只能改變指標，該如何處理？
- 如果有超過兩個節點被交換，能否推廣此方法？
- Morris Traversal 在修改樹結構的過程中是否線程安全？在多線程環境下有何替代方案？