Yes, Morris again. Praise Morris.

Traverse the tree only once with constant space.

No nasty global variables, and not really using the previous-first-second method.

```
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *s[3][2], *p, *h = root;
int v, n = 0;
bool f = false;
while (h) {
if (p = h->left) {
while (p->right && p->right != h) p = p->right;
if (p->right) {
s[n][1] = h;
if (h->val < v) n++;
s[n][0] = h;
v = h->val;
h = h->right;
p->right = NULL;
} else {
p->right = h;
h = h->left;
}
} else {
s[n][1] = h;
if (f && h->val < v) n++;
s[n][0] = h;
v = h->val;
h = h->right;
f = true;
}
}
if (n==2) swap(s[0][0]->val, s[1][1]->val);
else swap(s[0][0]->val, s[0][1]->val);
}
};
```