Class Solution

99. Recover Binary Search Tree/Solution.cpp:21–50

never use magic number !

// never use magic number !
class Solution {
private:
    TreeNode * sw1;
    TreeNode * sw2;
    TreeNode * prev;
public:
    Solution():sw1(NULL), sw2(NULL), prev(new TreeNode(1 << 31)) {}

    void traverse(TreeNode * root) {
        if (root == NULL) return ;
        traverse(root->left);
        // in-order traverse
        // edge case stack overfloe
        if (sw1 == NULL and prev->val >= root->val and root->val != (1 << 31)) sw1 = prev;
        if (sw1 != NULL and prev->val >= root->val) sw2 = root;
        prev = root;
        traverse(root->right);
    }

    void swap() {
        int tmp = sw1->val;
        sw1->val = sw2->val;
        sw2->val = tmp;
    }

    void recoverTree(TreeNode* root) {
        traverse(root);
        swap();
    }
};


int main() {