Recover Binary Search Tree.txt

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TreeNode *prev = NULL, *succ = NULL;
        TreeNode *l = findFirst(root, prev), *r = findLast(root, succ);
        int t = l->val;
        l->val = r->val;
        r->val = t;
    }
    TreeNode* findFirst(TreeNode* root, TreeNode*& prev) {
        if (!root)
            return NULL;
        TreeNode* l = findFirst(root->left, prev);
        if (l)
            return l;
        if (prev && (prev->val > root->val))
            return prev;
        prev = root;
        return findFirst(root->right, prev);
    }
    TreeNode* findLast(TreeNode* root, TreeNode*& succ) {
        if (!root)
            return NULL;
        TreeNode* r = findLast(root->right, succ);
        if (r)
            return r;
        if (succ && (root->val > succ->val))
            return succ;
        succ = root;
        return findLast(root->left, succ);
    }
};