LeetCode Recover Binary Search Tree：中序遍歷找出兩個錯誤節點

問題描述

一棵二叉搜索樹（BST）中有兩個節點被錯誤交換，請恢復樹的正確結構。要求常數空間（遞歸棧不算）。

核心性質：BST 中序遍歷 = 遞增序列

若兩個節點交換，中序序列會出現「逆序對」：

• 情況一：兩節點在中序中相鄰 → 僅出現一處 prev.val > curr.val。交換這兩個節點即可。
• 情況二：兩節點在中序中不相鄰 → 出現兩處逆序。第一處的 prev（較大值）和第二處的 curr（較小值）是被交換的兩個節點。

Morris 遍歷：真正的 O(1) 空間

遞歸/棧遍歷空間 O(h)。Morris 遍歷利用葉節點的空指針建立線索，無需額外空間。

Python 實現（遞歸版，簡潔易懂）

class Solution:
    def __init__(self):
        self.first = self.second = self.prev = None
    
    def recoverTree(self, root):
        self._inorder(root)
        self.first.val, self.second.val = self.second.val, self.first.val
    
    def _inorder(self, node):
        if not node: return
        self._inorder(node.left)
        if self.prev and node.val < self.prev.val:
            if not self.first:  # 第一處逆序
                self.first = self.prev
            self.second = node  # 最後一處逆序的 curr
        self.prev = node
        self._inorder(node.right)

C++ Morris 遍歷版（真 O(1) 空間）

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *prev = nullptr, *cur = root;
        while (cur) {
            if (!cur->left) {
                // 訪問 cur
                if (prev && cur->val < prev->val) {
                    if (!first) first = prev;
                    second = cur;
                }
                prev = cur;
                cur = cur->right;
            } else {
                // 找前驅
                TreeNode* pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;  // 建立線索
                    cur = cur->left;
                } else {
                    pre->right = nullptr; // 恢復樹
                    // 訪問 cur
                    if (prev && cur->val < prev->val) {
                        if (!first) first = prev;
                        second = cur;
                    }
                    prev = cur;
                    cur = cur->right;
                }
            }
        }
        swap(first->val, second->val);
    }
};

關鍵點總結

1. 中序遍歷線性化：BST → 有序數組，問題轉化為「數組中兩元素交換，恢復順序」。
2. 兩種逆序模式：相鄰交換（1處逆序）vs 非相鄰交換（2處逆序），統一處理邏輯：first = 第一處的 prev, second = 最後一處的 curr。
3. 空間優化：Morris 遍歷是樹類題目達成 O(1) 空間的標準技巧，值得熟練掌握。

複雜度

• 時間：O(n)，每個節點訪問常數次。
• 空間：遞歸版 O(h)，Morris 版 O(1)。