Skip to content

Instantly share code, notes, and snippets.

@sitano
Last active October 25, 2015 19:46
Show Gist options
  • Save sitano/92430299079ae1bb1f71 to your computer and use it in GitHub Desktop.
Save sitano/92430299079ae1bb1f71 to your computer and use it in GitHub Desktop.
O(1) space solution using Morris single threaded tree traversal to: two elements of a binary search tree (BST) are swapped by mistake, recover the tree without changing its structure.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
TreeNode* fst;
TreeNode* sec;
public:
void recoverTree(TreeNode* root) {
fix(root);
int tmp = fst->val;
fst->val = sec->val;
sec->val = tmp;
}
void fix(TreeNode *root) {
TreeNode *cur = root, *pre, *last = NULL;
if (!root) {
return;
}
while (cur) {
if (!cur->left) {
check(last, cur);
last = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right != NULL && pre->right != cur) {
pre = pre->right;
}
if (pre->right == NULL) {
pre->right = cur;
cur = cur->left;
} else {
check(last, cur);
last = cur;
pre->right = NULL;
cur = cur->right;
}
}
}
}
void check(TreeNode *last, TreeNode *cur) {
if (last != NULL && last->val > cur->val) {
if (!fst) {
fst = last;
sec = cur;
} else {
sec = cur;
}
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment