/**
 * When BFS tree traveled with in-order, it should generate and ascending array,
 * the two swapped elements would be:
 *     the first element that is larger than its in-order next,
 *     the last element that is less than its in-order previous.
 *
 * If two swapped elements are neighbor in in-order array, there is only one pair
 * that match above condition, otherwise there are two pairs
 */

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


void inOrderTraversal(TreeNode *n, TreeNode* &pre, TreeNode* &p, TreeNode* &q) {
    if (n == NULL) return;
    
    inOrderTraversal(n->left, pre, p, q);
    if (pre != NULL && pre->val > n->val) {
        // first time find node that larger than its next
        if (p == NULL) {
            p = pre;
        }

        // each time find node that less than its previous
        q = n;
    }

    pre = n;
    
    inOrderTraversal(n->right, pre, p, q);
}


void recoverTree(TreeNode *root) {
    TreeNode *pre = NULL;
    TreeNode *p = NULL;
    TreeNode *q = NULL;
    inOrderTraversal(root, pre, p, q);
    if (p != NULL && q != NULL) {
        int tmp = p->val;
        p->val = q->val;
        q->val = tmp;
    }
}