LeetCode 99：Recover Binary Search Tree（恢復二叉搜索樹）

一、題目描述

一棵二叉搜索樹（BST）中有兩個節點被錯誤交換，請在不改變樹結構的情況下恢復它。

進階： 能否用 O(1) 空間完成？（Morris 遍歷）

二、解題思路：中序遍歷找錯誤節點

BST 中序遍歷應為遞增序列。若兩節點交換，序列中會出現兩處「降序」：

• 第一處降序：前一個節點較大 → 第一個錯誤節點
• 第二處降序：後一個節點較小 → 第二個錯誤節點

例：正確序列 1,2,3,4,5，交換 2 和 5 → 1,5,3,4,2。降序點：5>3 和 4>2。錯誤節點為 5 和 2，交換其值即可恢復。

使用遞歸中序遍歷，維護 pre 指針指向前一訪問節點，發現 pre->val > curr->val 時記錄錯誤節點。

三、代碼實現（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mistake1 = nullptr;
    TreeNode* mistake2 = nullptr;
    TreeNode* pre = nullptr;

    void recoverTree(TreeNode* root) {
        inorder(root);
        if (mistake1 && mistake2) swap(mistake1->val, mistake2->val);
    }

private:
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (pre && pre->val > root->val) {
            if (!mistake1) {
                mistake1 = pre;
                mistake2 = root; // 相鄰交換時第二個錯誤節點就是當前節點
            } else {
                mistake2 = root; // 非相鄰交換，更新第二個錯誤節點
            }
        }
        pre = root;
        inorder(root->right);
    }
};

四、Morris 遍歷（O(1) 空間）

利用線索二叉樹思想，不使用棧和遞歸，通過修改空指針建立線索實現中序遍歷，遍歷後恢復樹結構。代碼較長，此處略過，感興趣可自行查閱。

五、複雜度分析

• 遞歸法：時間 O(N)，空間 O(H)
• Morris 遍歷：時間 O(N)，空間 O(1)