99_RecoverBinarySearchTree - a920604a/leetcode GitHub Wiki

class Solution {
public:
    void traverse(TreeNode *root, vector<TreeNode*>& list, vector<int>& vals) {
        if(!root) return ;
        
        traverse(root->left, list, vals);
        list.push_back(root);
        vals.push_back(root->val);
        traverse(root->right, list, vals);
        
    }
    void recoverTree(TreeNode* root) {
        // 只會有兩個節點放錯
        // 遍歷變存下來在對調
        vector<TreeNode*> list;
        vector<int> vals;
        traverse(root, list, vals);
        sort(vals.begin(), vals.end());      
        
        for(int i=0;i<list.size() ;++i){
            list[i]->val = vals[i];
        }
    }
};

class Solution {
public:
    TreeNode *prev = nullptr, *a = nullptr, *b = nullptr;
    void inorder(TreeNode *root){
        if(!root) return;
        inorder(root->left);
        if(prev && prev->val > root->val){
            if(!a) a = prev;
            b = root;
        }
        prev = root;
        inorder(root->right);
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(a->val,b->val);
        
    }
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *pre = nullptr, *a = nullptr, *b = nullptr;
        stack<TreeNode*>sta;
        TreeNode *p = root;
        while(p || !sta.empty()){
            while(p){
                sta.push(p);
                p=p->left;
            }
            p = sta.top();
            sta.pop();
            if (pre) {
                if (pre->val > p->val) {
                    if (!a) a = pre;
                    b = p;
                }
            }
            pre = p;
            p=p->right;
        }
        swap(a->val, b->val);
        
    }
};