LeetCode 99 Recover Binary Search Tree：中序遍歷定位兩個錯誤節點

問題描述

二叉搜索樹 (BST) 中有兩個節點被錯誤交換，恢復樹結構不變、值正確。要求 O(1) 空間（不計遞歸棧）。

核心洞察：BST 中序遍歷為有序序列

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

• 相鄰交換：如 1 3 2 4 5 → 一處逆序 (3,2)
• 非相鄰交換：如 1 5 3 4 2 → 兩處逆序 (5,3) 和 (4,2)

第一個逆序對的前一個節點、最後一個逆序對的後一個節點即為兩個錯誤節點。

O(1) 空間中序遍歷（遞歸版，棧空間不計）

class Solution {
    TreeNode *pre = nullptr, *p1 = nullptr, *p2 = nullptr;
    
    void helper(TreeNode* root) {
        if (!root) return;
        helper(root->left);
        if (pre && pre->val > root->val) {  // 發現逆序
            if (!p1) { p1 = pre; p2 = root; }  // 第一處逆序
            else { p2 = root; }                // 第二處逆序
        }
        pre = root;
        helper(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        helper(root);
        swap(p1->val, p2->val);
    }
};

Morris 遍歷：真正的 O(1) 空間（含遞歸棧）

利用線索二叉樹思想，無需棧、無需遞歸：

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

複雜度對比

總結

本題核心在於利用 BST 中序遍歷有序性，將「兩節點交換」轉化為「有序數組兩元素交換」的逆序對檢測問題。遞歸版代碼簡潔且面試足夠；Morris 遍歷展示了線索二叉樹技巧，是 O(1) 空間樹遍歷的標準解法。