Simple recursive C++ solution, an iterative Morris solution is also enclosed

• using reference to pointer instead of pointer to pointer

``````class Solution {
private:
void traverse(TreeNode* root, TreeNode*& pre, TreeNode*& first, TreeNode*& second)
{
if(!root) return ;
traverse(root->left, pre, first, second);
if(pre && pre->val>root->val)
{
if(!first) first = pre;
second = root;
}
pre = root;
traverse(root->right, pre, first, second);
}
public:
void recoverTree(TreeNode* root)
{
TreeNode *first = NULL, *second = NULL, *pre = NULL;
traverse(root, pre, first, second);
if(first) swap(first->val, second->val);
}
};
``````

• An iterative solution is enclosed here, accepted as best

``````class Solution {
public:
void recoverTree(struct TreeNode* root)
{
struct TreeNode *pre=NULL, *first=NULL, *second=NULL;
struct TreeNode *t = NULL;
while(root)
{
if(root->left)
{
t = root->left;
while(t->right && t->right!=root) t = t->right;
if(t->right)
{
if(pre && pre->val > root->val)
{
if(!first)
{
first = pre;
second = root;
}
else second = root;
}
pre = root;
t->right = NULL;
root = root->right;
}
else
{
t->right = root;
root = root->left;
}
}
else
{
if(pre && pre->val > root->val)
{
if(!first) first=pre, second=root;
else second = root;
}
pre = root;
root = root->right;
}
}
if(first && second)
{
first->val += second->val;
second->val = first->val-second->val;
first->val -= second->val;
}
}
};``````

• Another version of the iterative - also Morris Traversal

``````class Solution {
public:
void recoverTree(struct TreeNode* root)
{
TreeNode *pre=NULL, *first=NULL, *second=NULL;
while(root)
{
if(!root->left)
{
if(pre && pre->val > root->val)
{
if(!first) first = pre;
second = root;
}
pre = root;
root = root->right;
}
else
{
TreeNode *t = root->left;
while(t->right && t->right!=root) t = t->right;
if(!t->right)
{
t->right = root;
root = root->left;
}
else
{
t->right = NULL;
if(pre && pre->val > root->val)
{
if(!first) first = pre;
second = root;
}
pre = root;
root = root->right;
}
}
}
if(first && second)
swap(first->val, second->val);
}
};``````

• recursive version becomes more clean now.

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