LeetCode Recover Binary Search Tree：兩種 O(1) 空間解法詳解

問題描述

一棵二叉搜索樹（BST）中有兩個節點被錯誤交換，要求在不改變樹結構的前提下恢復樹。進階要求：O(1) 額外空間（遞歸棧不算）。

核心觀察

BST 中序遍歷為遞增序列。兩個節點交換會導致序列中出現兩處逆序：
- 第一處逆序：前驅節點值 > 當前節點值 → **前驅節點是第一個錯誤節點**。
- 第二處逆序：前驅節點值 > 當前節點值 → **當前節點是第二個錯誤節點**。
若兩錯誤節點相鄰，只出現一次逆序，則第一個錯誤節點是前驅，第二個是當前。

解法一：遞歸中序遍歷（隱式棧，視為 O(1) 額外空間）

class Solution {
public:
    void recoverTree(TreeNode *root) {
        if (!root) return;
        TreeNode *pre = nullptr, *n1 = nullptr, *n2 = nullptr;
        findTwoNode(root, n1, n2, pre);
        if (n1 && n2) swap(n1->val, n2->val);
    }

    void findTwoNode(TreeNode* root, TreeNode* &n1, TreeNode* &n2, TreeNode* &pre) {
        if (!root) return;
        findTwoNode(root->left, n1, n2, pre);
        if (pre && pre->val > root->val) {
            n2 = root;              // 第二個錯誤節點總是當前
            if (!n1) n1 = pre;      // 第一個錯誤節點是第一次逆序的前驅
        }
        pre = root;
        findTwoNode(root->right, n1, n2, pre);
    }
};

解法二：Morris 遍歷 / 顯式棧模擬（真正 O(1) 空間）

這裡給出顯式棧版本，邏輯相同：

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void recoverTree(TreeNode *root) {
        if (!root) return;
        stack s;
        TreeNode *p = root, *pre = nullptr, *n1 = nullptr, *n2 = nullptr;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (pre && pre->val > p->val) {
                if (!n1) n1 = pre;
                n2 = p;
            }
            pre = p;
            p = p->right;
        }
        if (n1 && n2) swap(n1->val, n2->val);
    }
};

關鍵點總結

• 中序遍歷獲取有序序列是 BST 題的通用切入點。
• 只需記錄 `pre`、`first`、`second` 三個指針，空間 O(1)。
• 遞歸版代碼簡潔，棧深度 O(h) 通常可接受；Morris 遍歷可完全消除棧但代碼複雜。
• 交換節點值而非節點本身，保持樹結構不變。

複雜度

• 時間：O(n) — 遍歷所有節點。
• 空間：遞歸/顯式棧 O(h)，Morris O(1)。