Question
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Stats
| Frequency | 2 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is one of the most difficult questions that I have solved.
The question can be solved using 2 pointers to point to the 2 misplaced nodes, and swap them. I solved the problem with this approach, and I found a good explanation here.
Only two variables (first, second) are enough to record nodes to be exchanged.
If there’s only one descending order pair (e.g. 20, 10, 30, 40, 50), use first & second to record it.
If there are two descending order pairs (e.g. 10, 40, 30, 20, 50 or 50, 20, 30, 40, 10), use the smaller number in second pair to update variable ‘second’.
In the end, swap first and second.
This is a popular solution on the Internet, which uses O(1) space, plus average case O(lgn) stack space (because recursion always incur stack usage). So this solution is actually not fulfilling the requirements.
中序遍历二叉树的空间复杂度是 O(logN) on average case
So finally I found a solution with constent space, and it’s using Treaded Binary Tree again! Look below for details.
Solution
This is a systematic analysis of Morris Traversal based on Threaded Binary Tree.
A solution of using Morris Traversal is explained here. Don’t worry about the tree structure being changed, because it’s reverted back after the traversal.
算法 2：为了满足 O(1)空间复杂度，我们就要使用非递归且不使用栈的中序遍历算法，在 leetcode 另一个题目 Binary Tree Inorder Traversal 中，我们提到了 Morris Traversal 中序遍历算法，它既没有递归，也没有使用栈，而是用了线索二叉树的思想，用闲置的右节点指向中序序列中该节点的后缀，遍历后再恢复树的原始指针。其主要算法步骤如下：
重复以下 1、2 直到当前节点为空。
Another person have a very good (maybe better) English version of analysis and code:
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
Code
First, my code (2 pointer solution)
TreeNode first = null, second = null;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
helper(root);
// now first and second are both found
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void helper(TreeNode root) {
if (root == null) return;
helper(root.left);
if (pre.val > root.val) {
if (first == null) {
first = pre;
second = root;
}
else second = root;
}
pre = root;
helper(root.right);
}
Second, real O(1) space solution using Threaded Binary Tree (i.e. Morris Traversal) in C++. I could not memorize this code.
void recoverTree(TreeNode *root) {
TreeNode *f1=NULL, *f2=NULL;
TreeNode *current,*pre, *parent=NULL;
if(root == NULL)
return;
bool found = false;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
if(parent && parent->val > current->val)
{
if(!found)
{
f1 = parent;
found = true;
}
f2 = current;
}
parent = current;
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
if(parent->val > current->val)
{
if(!found)
{
f1 = parent;
found = true;
}
f2 = current;
}
parent = current;
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
if(f1 && f2)
swap(f1->val, f2->val);
}