1 /**
 2  * Definition for binary tree
 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 public:
12     TreeNode *err_1, *err_2;
13     TreeNode *pre;
14     
15     void find2Nodes(TreeNode *root) {
16         if (root == NULL) return;
17         
18         if (root->left != NULL) {
19             find2Nodes(root->left);
20         }
21         if (pre != NULL && pre->val >= root->val) {
22             if (err_1 == NULL) err_1 = pre;
23             err_2 = root;
24         }
25         pre = root;
26         if (root->right != NULL) {
27             find2Nodes(root->right);
28         }
29     }
30     
31     void recoverTree(TreeNode *root) {
32         if (root == NULL) return;
33         
34         err_1 = err_2 = pre = NULL;
35         
36         find2Nodes(root);
37         swap(err_1->val, err_2->val);
38     }
39 };