Note: 1. Given a sequence `{1, 4, 3, 7, 9}`

, you find pair `4(!<=)3`

, swap this pair and sequence is in order.

2. Given a sequence `{1, 9, 4, 5, 3, 10}`

, you get first pair `9(!<=)4`

and second pair `5(!<=)3`

, swap pair `9(!<=)3`

and sequence is in order.

3. Given a sequence, only in two above (general) cases, that you can just swap one pair numbers to convert an unordered sequence into ordered.

4. You can tranverse BST inorder to get above sequence.

So, my alg is:

```
void recover(TreeNode *root, TreeNode *&pre, TreeNode *&a, TreeNode *&b) {
if (root)
{
recover(root->left, pre, a, b);
if (root->val < pre->val)
{
if (!a) a = pre; //a should change once.
b = root; //b could change twice.
}
pre = root;
recover(root->right, pre, a, b);
}
}
void recoverTree(TreeNode *root) {
if (!root) return;
TreeNode p(numeric_limits<int>::min());
TreeNode *a, *b, *pre;
a = b = 0;
pre = &p;
recover(root, pre, a, b);
if (a && b)
{
swap(a->val, b->val);
}
return;
}
```

I think this problem requirement is strange. Does O(1) space complexity algorithm exists?

1. Does BST should be tranversed?

2. If answer of `1`

is true, I don't think an O(1) space complexity exists, for there does not exists a BST tranverse algorithm taking O(1) space complexity.

3. If answer of `1`

is false, I just wonder how can you find the disordered pair.