Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

Recover Binary Search Tree.cpp

/**
 * 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
        vector<TreeNode*> array;
        inOrder(array, root);
        int left = -1;
        int right = -1;
        
        for(int i = 0; i < array.size() - 1; ++i) {
            if(array[i]->val > array[i + 1]->val) {
                if(left == -1) {
                    left = i;
                    right = i + 1;
                } else {
                    right = i + 1;
                    break;
                }
            }
        }
        
        int tmp = array[left]->val;
        array[left]->val = array[right]->val;
        array[right]->val = tmp;
        
    }
    
    void inOrder(vector<TreeNode*>& array, TreeNode* root) {
        if(root == NULL) {
            return;
        }
        
        inOrder(array, root->left);
        array.push_back(root);
        inOrder(array, root->right);
    }
};