99

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first, *second, *pred, *tmp;
        first = second = pred = NULL;
        bool firstNode = true;

        // Morris Inorder Traversal.
        TreeNode *current = root;
        while(current){
            if(!current->left){
                // Visit current.
                if(pred && pred->val > current->val){
                    second = current;
                    if(!first) first = pred;
                }
                pred = current;
                current = current->right;
            }
            else{
                // Find Predecessor, here tmp is predecessor.
                tmp = current->left;
                while(tmp->right && tmp->right != current)
                    tmp = tmp->right;

                // Set right of predecessor to current.
                if(!tmp->right){
                    tmp->right = current;
                    current = current->left;
                }
                else{
                    tmp->right = NULL;
                    // Visit current.
                    if(pred && pred->val > current->val){
                        second = current;
                        if(!first) first = pred;
                    }
                    pred = current;
                    current = current->right;
                }
            }
        }
        swap(first->val, second->val);
    }
};