```
class Solution {
public:
// Morris Inorder Traversal
void recoverTree(TreeNode *root) {
vector<TreeNode *> record;
TreeNode *curr = root, *prev = nullptr;
while (curr != nullptr) {
if (curr->left == nullptr) {
if (!isCompatible(curr, prev)) record.push_back(curr);
prev = curr;
// @ jump back to the low level node.
curr = curr->right;
}
else {
// @ left subtree.
auto node = curr->left;
// @ move to the largest right child of the left subtree.
while (node->right != nullptr && node->right != curr) node = node->right;
if (node->right == nullptr) {
node->right = curr; // @ create the link from node to curr.
curr = curr->left;
}
else { // prev->right == curr
if (!isCompatible(curr, prev)) record.push_back(curr);
node->right = nullptr; // @ remove the link between node and curr.
prev = curr;
curr = curr->right;
}
}
}
swap(record[0]->val, record[1]->val);
}
private:
bool isCompatible(TreeNode *curr, TreeNode *prev) {
int left = prev ? prev->val : INT_MIN;
int right = curr->right ? curr->right->val : INT_MAX;
return (left < curr->val && curr->val < right) || (left > curr->val && curr->val > right);
}
};
```

Input is {1,#,2,3}