Recover Binary Search Tree

• Time : O(n)
• Space : O(1)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

 void dfs(TreeNode* A, int& small, vector<int>& res) {
     if(A == NULL) return;
     dfs(A->left, small, res);
     if(small > A->val) {
         if(res.empty()) {
             res.push_back(small);
             res.push_back(A->val);
         } else res.back() = A->val;
     }
     small = A->val;
     dfs(A->right, small, res);
 }
vector<int> Solution::recoverTree(TreeNode* A) {
    vector<int> res;
    int small = INT_MIN;
    dfs(A,small,res);
    sort(begin(res),end(res));
    return res;
}