1
class Solution {
2
 public:
3
  vector<int> v;
4
  int i = 0;
5
  void inorder(TreeNode *root) {
6
    if (!root) return;
7
    inorder(root->left);
8
    v.push_back(root->val);
9
    inorder(root->right);
10
  }
11
  void check(TreeNode *root) {
12
    if (!root) return;
13
    check(root->left);
14
    if (v[i] != root->val) swap(v[i], root->val);
15
    i++;
16
    check(root->right);
17
  }
18
  void recoverTree(TreeNode *root) {
19
    inorder(root);
20
    sort(v.begin(), v.end());
21
    check(root);
22
  }
23
};