Recover Binary Search Tree Solutions in C++

// Source : https://oj.leetcode.com/problems/recover-binary-search-tree/
// Author : Hao Chen
// Date   : 2014-10-11



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

//
// We can convert the BST to a sorted array,  then we can find the two nodes which missed the order.
//
// To cover the BST to sorted array, we needn't use an extra array, we just traverse the tree in order.
//  
//                   8
//           _______/ \_______
//          /                 \
//         4                  12
//      __/ \__             __/ \__
//     /       \           /       \
//    2         6        10        14
//   / \       / \       / \       / \
//  1   3     5   7     9  11    13  15
//  
//  
class Solution {
public:
    void recoverTreeHelper(TreeNode *root) {
        
        if (root == NULL) return;
        
        recoverTreeHelper(root->left);
        if (prev) {
            if (prev->val > root->val){
                if (n1==NULL) {
                    n1 = prev;
                }
                n2 = root;
            }
        }
        prev = root;
        recoverTreeHelper(root->right);
    }
    
    void recoverTree(TreeNode *root) {
        n1 = n2 = prev = NULL;
        recoverTreeHelper(root);
        if (n1 && n2) {
            swap(n1->val, n2->val);
        }
    }
private:
    TreeNode *n1, *n2, *prev;
};

#include <cstddef>
#include <algorithm>

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

class Solution {
    void InorderTraversal(TreeNode *root, TreeNode **prev, TreeNode **first, TreeNode **second) {
        if (root == NULL) return;
        InorderTraversal(root->left, prev, first, second);
        if (*prev && (*prev)->val > root->val) {
            if (*first == NULL) *first = *prev;
            *second = root;
        }
        *prev = root;
        InorderTraversal(root->right, prev, first, second);
    }
public:
    void recoverTree(TreeNode *root) {
        TreeNode *prev = NULL, *first = NULL, *second = NULL;
        InorderTraversal(root, &prev, &first, &second);
        if (first && second) std::swap(first->val, second->val);
    }
};