LeetCode 99 Recover Binary Search Tree：中序遍歷找錯誤節點

LeetCode 99 Recover Binary Search Tree：中序遍歷找錯誤節點

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

核心觀察

BST 中序遍歷應為遞增序列。兩節點交換導致序列中出現兩處逆序（或相鄰一處）。

• 第一處逆序：前一個節點 first（較大值）。
• 第二處逆序：後一個節點 second（較小值）。
• 若交換節點相鄰，僅一處逆序，first 為前節點，second 為後節點。

優化版：單次中序遍歷記錄兩節點

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *pre = nullptr;
        stack st;
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            while (cur) { st.push(cur); cur = cur->left; }
            cur = st.top(); st.pop();
            if (pre && pre->val > cur->val) {
                if (!first) first = pre;  // 第一次逆序，pre 是較大者
                second = cur;             // 最後一次逆序，cur 是較小者
            }
            pre = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};

Morris 遍歷（O(1) 空間）

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

關鍵點

• 中序遍歷時維護 pre 指針，比較 pre->val > cur->val 檢測逆序。
• first 只記錄第一次逆序的 pre，second 每次逆序都更新為 cur，最終指向最後逆序的較小值。
• 交換兩節點值而非節點本身，結構不變。

複雜度

此題是 BST 性質與中序遍歷結合的經典應用，Morris 遍歷展示了線索二叉樹思想，是樹算法進階必修內容。