# REAL O(1) Space (No recursion/No stack, etc) O(n) Time solution. 48ms C++

• Someone complained that a recursion solution isn't really a O(1) space solution. Ok, here comes the real O(1) solution. No recursion, no stack. Pure Morris traversal. 48 ms, C++ :

``````class Solution {
TreeNode * wrong_node0 = nullptr, * wrong_node1 = nullptr, * prev = nullptr;
void verify(TreeNode * cur)
{
if (prev != nullptr && prev -> val > cur -> val)
{
if (wrong_node0 == nullptr)
{
wrong_node0 = prev;
wrong_node1 = cur; // in case the tree has only 2 elements.
}
else
wrong_node1 = cur;
}
prev = cur;
}
void morrisInorder(TreeNode * root)
{
TreeNode * cur = root;
while (cur)
{
if (cur->left == nullptr)
{
verify(cur);
cur = cur->right;
continue;
}
TreeNode * pred = cur->left;
while (pred -> right != nullptr && pred -> right != cur)
pred = pred -> right; //finding predecessor
if (pred -> right == nullptr)
{
pred -> right = cur;
cur = cur -> left;
}else {//pred -> right == cur;
pred -> right = nullptr;
verify(cur);
cur = cur -> right;
}
}
}
public:
void recoverTree(TreeNode* root) {
morrisInorder(root);
swap(wrong_node0->val, wrong_node1->val);
}
};``````

• where are the explanation then?

• First of all, the title doesn't say "with explanation". So it is legitimate to not post the expiation.
Second, it also says it is using Morris Traversal. I think this explains everything.

• Previously it is not ok to post solutions without any explanation. Quote:
`closed with the note: Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the [Discuss FAQ](http://oj.leetcode.com/discuss/faq) for more info. Take a look at [good sharing example](https://oj.leetcode.com/discuss/8092/my-dp-o-n-solution-without-using-stack)` See.https://leetcode.com/discuss/10283/my-solution-in-c-dfs But now no one cares.

• I also said, it was "Pure Morris traversal". I think this is explanatory enough. I don't think people who thought about this question don't understand it.

• What kind of name "fentoyal" is...

• What kind of question "What kind of name "fentoyal" is..." is??

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