LeetCode Recover Binary Search Tree：中序遍歷找兩個錯誤節點 O(1) 空間 Morris 遍歷

問題描述

BST 中兩個節點被錯誤交換，恢復樹結構不變、值正確。要求 O(1) 空間（Morris 遍歷）或 O(h) 空間（遞歸/棧）。

核心觀察：中序遍歷應遞增

正確 BST 中序遍歷嚴格遞增。交換兩節點後，中序序列會有一處或兩處逆序：

• 相鄰交換：... 3 2 4 ... → 一處逆序 (3,2)。
• 非相鄰交換：... 5 ... 2 ... → 兩處逆序 (5,2) 和 (4,5?) 實際為 (5,2) 和 (3,4?) 需仔細分析。

統一規律：第一個逆序的前一個節點 和 最後一個逆序的後一個節點 即為兩個錯誤節點。

遞歸版（O(h) 空間，易理解）

void recoverTree(TreeNode* root) {
    TreeNode *pre = nullptr, *n1 = nullptr, *n2 = nullptr, *cur = root;
    while (cur) {
        if (!cur->left) {
            // 訪問 cur
            if (pre && pre->val > cur->val) {
                n1 = cur; if (!n2) n2 = pre;
            }
            pre = cur;
            cur = cur->right;
        } else {
            // 找前驅
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) pred = pred->right;
            if (!pred->right) {
                pred->right = cur;  // 建立線索
                cur = cur->left;
            } else {
                pred->right = nullptr;  // 恢復
                // 訪問 cur
                if (pre && pre->val > cur->val) {
                    n1 = cur; if (!n2) n2 = pre;
                }
                pre = cur;
                cur = cur->right;
            }
        }
    }
    swap(n1->val, n2->val);
}

關鍵點總結

1. 兩節點定位：n1 為最後一次逆序的 cur，n2 為第一次逆序的 pre。
2. 僅交換值：題目要求結構不變，直接 swap(val)。
3. Morris 核心：利用葉子節點右指針為空，建立線索指向後繼，遍歷後恢復。
4. 邊界：樹至少 2 節點，保證有解。

複雜度

• 遞歸：時間 O(n)，空間 O(h)（最壞 O(n)）。
• Morris：時間 O(n)，空間 O(1)。