# My C++ O(1) space in order traval

• Simple in order travel, use constant space to keep track of some recent visited nodes.
At each step, check if the order is correct, if it isn't then there's something wrong, record it.
Finally check these suspicious situation and find the swapped values;

``````class Solution {
public:
int a, b, c;
TreeNode * x, * y, * z;
vector<TreeNode *> swaps;

void check_for_swap()
{
if (y && z)
if (b > c)
{
// the order here is not correct, take a note
swaps.push_back(y);
swaps.push_back(z);
}
}

// in order travel
void travel(TreeNode * n)
{
// go left
if (n->left)
travel(n->left);

// visit
// update recent values
a = b;
b = c;
c = n->val;

x = y;
y = z;
z = n;

check_for_swap();

// go right
if (n->right)
travel(n->right);
}

void recoverTree(TreeNode *root) {

a = -1;
b = -1;
c = -1;
x = NULL;
y = NULL;
z = NULL;

travel(root);

// if the swaped elements are adjacent, then swaps.size() == 2
// else swaps.size() == 4, the swaped nodes are the 1st and the last one, so:
if (swaps.size() == 4)
{
swaps.erase(swaps.begin() + 1);
swaps.erase(swaps.begin() + 1);
}
if (swaps.size() == 2)
{
int v = swaps[0]->val;
swaps[0]->val = swaps[1]->val;
swaps[1]->val = v;
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.