LeetCode 99. 恢復二叉搜索樹：O(1) 空間 Morris 中序遍歷變體

題目描述

二叉搜索樹（BST）中有兩個節點被錯誤交換。在不改變樹結構前提下恢復樹。要求常數空間複雜度（即不可使用 O(n) 遞歸棧或顯式棧）。

核心觀察：中序遍歷應有序

BST 中序遍歷為遞增序列。兩個節點交換後，序列中會出現一處或兩處逆序：

• 相鄰交換：... 3, 2, 4 ... → 一處逆序 (3,2)，交換 3 和 2。
• 非相鄰交換：... 5, 3, 4, 2, 6 ... → 兩處逆序 (5,3) 和 (4,2)，交換 5 和 2。

O(1) 空間解法：遞歸中序 + 全局指針

雖遞歸棧佔 O(h) 空間，但題目通常接受「不額外分配 O(n) 數組」的遞歸寫法。真正 O(1) 需 Morris 遍歷，此處給出工程常用遞歸版：

void recoverTree(TreeNode* root) {
    TreeNode *first = nullptr, *second = nullptr, *prev = nullptr, *cur = root;
    while (cur) {
        if (!cur->left) {
            // 訪問 cur
            if (prev && prev->val > cur->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 && prev->val > cur->val) {
                    if (!first) first = prev;
                    second = cur;
                }
                prev = cur;
                cur = cur->right;
            }
        }
    }
    swap(first->val, second->val);
}

關鍵點總結

• 利用 BST 中序有序性，將問題轉化為「找出亂序數組中兩個交換元素」。
• 兩個指針 first、second 分別記錄第一處逆序的前節點和最後一處逆序的後節點。
• Morris 遍歷通過修改右指針建立線索，實現無棧中序遍歷，遍歷後恢復指針。