99. Recover Binary Search Tree

My initial idea is to output all nodes into an array. Since it is a binary search tree, an in-order traversal should get us a sorted array. All we need to do then is to find two nodes that are out of order and swap then. The easy mistake to make is to use if else clause in finding the two node. Note these two nodes are not exclusive to each other, so we shouldn't do "else".

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  private:  
12:    vector<TreeNode*> res;  
13:  public:  
14:    void recoverTree(TreeNode* root) {  
15:      helper(root);  
16:      TreeNode *first = NULL, *second = NULL;  
17:      for (int i = 0; i < res.size()-1; i++) {  
18:        if (first == NULL && res[i]->val > res[i+1]->val) {  
19:          first = res[i];  
20:        }  
21:        if (first != NULL && res[i]->val > res[i+1]->val) {  
22:          second = res[i+1];  
23:        }  
24:      }  
25:      swap(first->val, second->val);  
26:    }  
27:    void helper(TreeNode* root) {  
28:      if (root == NULL) return;  
29:      helper(root->left);  
30:      res.push_back(root);  
31:      helper(root->right);  
32:    }  
33:  };  

There is another way to find out the two out-of-order nodes within the in-order traversal. It's very important to let the previous node be a global variable. Because when you are traversing left child, when you are done, you want the previous node to be the left child. If you pass the previous node to the recursion, you are only considering the case of right child.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  private:  
12:    TreeNode *first = NULL;  
13:    TreeNode *second = NULL;  
14:    TreeNode *prev = new TreeNode(INT_MIN);  
15:  public:  
16:    void recoverTree(TreeNode* root) {  
17:      helper(root);  
18:      swap(first->val, second->val);  
19:    }  
20:    void helper(TreeNode *root) {  
21:      if (root == NULL) return;  
22:      helper(root->left);  
23:      if (first == NULL && prev->val >= root->val) first = prev;  
24:      if (first != NULL && prev->val >= root->val) second = root;  
25:      prev = root;  
26:      helper(root->right);  
27:    }  
28:  };