Yu's Coding Garden : leetcode Question 75: Recover Binary Search Tree
So the easiest way is inorder traverse the BST and find the element pair (two elements) which are not consistent with the definition of BST. In order to get the order, a queue is needed, which is O(n).
Now how to do this procedure in O(1)?
What we need is actually two pointers, which point to 2 tree nodes where is incorrect. Therefore, we only need to store these two pointers, and, we also need another pointer to store the previous element, in order to compare if the current element is valid or not.
The time complexity is O(n). But the space complexity is not constant, since we use recursive function.
http://www.cnblogs.com/yuzhangcmu/p/4208319.html
X. Iterative Version:
https://discuss.leetcode.com/topic/24975/java-solution-with-in-order-traversal/2
X. O(nlogn)
https://discuss.leetcode.com/topic/29297/18ms-java-solution-with-in-order-traversal-and-sorting-o-nlogn-time-and-o-n-space
X. Using Morris traverse:
To find out the bad nodes, we have to perform an inorder traversal. So the question becomes: Can we conduct an inorder traversal with constant space usage?
Morris Traversal, that implement inorder traversal without recursion or stack.
http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1 \ 2
Example 2:
Input: [3,1,4,null,null,2] 3 / \ 1 4 / 2 Output: [2,1,4,null,null,3] 2 / \ 1 4 / 3
Follow up:
- A solution using O(n) space is pretty straight forward.
- Could you devise a constant space solution?
So the easiest way is inorder traverse the BST and find the element pair (two elements) which are not consistent with the definition of BST. In order to get the order, a queue is needed, which is O(n).
Now how to do this procedure in O(1)?
What we need is actually two pointers, which point to 2 tree nodes where is incorrect. Therefore, we only need to store these two pointers, and, we also need another pointer to store the previous element, in order to compare if the current element is valid or not.
The time complexity is O(n). But the space complexity is not constant, since we use recursive function.
https://leetcode.com/problems/recover-binary-search-tree/discuss/32535/No-Fancy-Algorithm-just-Simple-and-Powerful-In-Order-Traversal
http://www.jiuzhang.com/solutions/recover-binary-search-tree/
If a binary tree is a BST, its inorder traversal should be in ascending order. We may use this property to solve this problem. Consider the following case:
For the inorder traversal list 123456, if 2 and 6 are swapped, the list becomes
163452. So when we scan the list, our goal is to mark the two swapped numbers and swap them back. So we can use two pointers, p and q. We compare the current value with the previous one, so when we see the first descending value, which is 3, the p pointer points to the previous node before 3, which is 6. When the next time we see the descending order again, which is 2, we use q pointer points to 2. Then we can swap the two numbers.
Do we consider all the case? Actually there is still a case we did not consider. For the two numbers in adjacent, e.g. 123456, where 34 are swapped, so now it is 124356. The first time it encounters a descending order is at 3, where we point p to 4, the one before 3, then there is no other descending later. So where is q? So we should point q to this current position.
https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal
This question appeared difficult to me but it is really just a simple in-order traversal! I got really frustrated when other people are showing off Morris Traversal which is totally not necessary here.
Let's start by writing the in order traversal:
private void traverse (TreeNode root) {
if (root == null)
return;
traverse(root.left);
// Do some business
traverse(root.right);
}
So when we need to print the node values in order, we insert System.out.println(root.val) in the place of "Do some business".
What is the business we are doing here?
We need to find the first and second elements that are not in order right?
We need to find the first and second elements that are not in order right?
How do we find these two elements? For example, we have the following tree that is printed as in order traversal:
6, 3, 4, 5, 2
We compare each node with its next one and we can find out that 6 is the first element to swap because 6 > 3 and 2 is the second element to swap because 2 < 5.
Really, what we are comparing is the current node and its previous node in the "in order traversal".
Let us define three variables, firstElement, secondElement, and prevElement. Now we just need to build the "do some business" logic as finding the two elements. See the code below:
TreeNode firstElement = null;
TreeNode secondElement = null;
// The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// In order traversal to find the two elements
traverse(root);
// Swap the values of the two nodes
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
private void traverse(TreeNode root) {
if (root == null)
return;
traverse(root.left);
// Start of "do some business",
// If first element has not been found, assign it to prevElement (refer to 6 in the example above)
if (firstElement == null && prevElement.val >= root.val) {
firstElement = prevElement;
}
// If first element is found, assign the second element to the root (refer to 2 in the example above)
if (firstElement != null && prevElement.val >= root.val) {
secondElement = root;
}
prevElement = root;
// End of "do some business"
traverse(root.right);
}
private TreeNode first;
private TreeNode second;
private TreeNode pre;
public void recoverTree(TreeNode root) {
if(root==null) return;
first = null;
second = null;
pre = null;
inorder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);
if(first==null && (pre==null ||pre.val>=root.val)){
first = pre;
}
if(first!=null && pre.val>=root.val){
second = root;
}
pre = root;
inorder(root.right);
}http://www.jiuzhang.com/solutions/recover-binary-search-tree/
If a binary tree is a BST, its inorder traversal should be in ascending order. We may use this property to solve this problem. Consider the following case:
For the inorder traversal list 123456, if 2 and 6 are swapped, the list becomes
163452. So when we scan the list, our goal is to mark the two swapped numbers and swap them back. So we can use two pointers, p and q. We compare the current value with the previous one, so when we see the first descending value, which is 3, the p pointer points to the previous node before 3, which is 6. When the next time we see the descending order again, which is 2, we use q pointer points to 2. Then we can swap the two numbers.
Do we consider all the case? Actually there is still a case we did not consider. For the two numbers in adjacent, e.g. 123456, where 34 are swapped, so now it is 124356. The first time it encounters a descending order is at 3, where we point p to 4, the one before 3, then there is no other descending later. So where is q? So we should point q to this current position.
TreeNode p,q; TreeNode prev = null; public void recoverTree(TreeNode root) { inOrderTraversal(root); int temp = p.val; p.val = q.val; q.val = temp; } private void inOrderTraversal(TreeNode root) { if (root == null) return; inOrderTraversal(root.left); if (prev != null && root.val < prev.val) { if (p == null) { p = prev; q = root; } else { q = root; } } prev = root; inOrderTraversal(root.right); } TreeNode firstElement = null;
TreeNode secondElement = null;
// The reason for this initialization is to avoid null pointer exception in the first comparison when prevElement has not been initialized
TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
// In order traversal to find the two elements
traverse(root);
// Swap the values of the two nodes
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
private void traverse(TreeNode root) {
if (root == null)
return;
traverse(root.left);
// Start of "do some business",
// If first element has not been found, assign it to prevElement (refer to 6 in the example above)
if (firstElement == null && prevElement.val >= root.val) {
firstElement = prevElement;
}
// If first element is found, assign the second element to the root (refer to 2 in the example above)
if (firstElement != null && prevElement.val >= root.val) {
secondElement = root;
}
prevElement = root;
// End of "do some business"
traverse(root.right);
}
例如1,4,3,2,5,6
1.当我们读到4的时候，发现是正序的，不做处理
2.但是遇到3时，发现逆序，将4存为第一个错误节点，3存为第二个错误节点
3.继续往后，发现3，2又是逆序了，那么将第2个错误节点更新为2
如果是这样的序列：1,4,3,5,6同上，得到逆序的两个节点为4和3。
========================================
这里我们补充一下，为什么要替换第二个节点而不是第一个节点：
e.g. The correct BST is below:
The inorder traversal is : 1 3 4 6 7 8 10 13 14
Find the place which the order is wrong.
Wrong order: 1 3 8 6 7 4 10 13 14
FIND: 8 6
Then we find: 7 4
8, 6 是错误的序列, 但是，7，4也是错误的序列。
因为8，6前面的序列是正确的，所以8，6一定是后面的序列交换来的。
而后面的是比较大的数字，也就是说8一定是被交换过来的。而7，4
中也应该是小的数字4是前面交换过来的。
用反证法来证明：
假设：6是后面交换过来的
推论: 那么8比6还大，那么8应该也是后面交换来的，
这样起码有3个错误的数字了
而题目是2个错误的数字，得证，只应该是8是交换过来的。
结论就是：我们需要交换的是：8， 4.
e.g. The correct BST is below:
The inorder traversal is : 1 3 4 6 7 8 10 13 14
Find the place which the order is wrong.
Wrong order: 1 3 8 6 7 4 10 13 14
FIND: 8 6
Then we find: 7 4
8, 6 是错误的序列, 但是，7，4也是错误的序列。
因为8，6前面的序列是正确的，所以8，6一定是后面的序列交换来的。
而后面的是比较大的数字，也就是说8一定是被交换过来的。而7，4
中也应该是小的数字4是前面交换过来的。
用反证法来证明：
假设：6是后面交换过来的
推论: 那么8比6还大，那么8应该也是后面交换来的，
这样起码有3个错误的数字了
而题目是2个错误的数字，得证，只应该是8是交换过来的。
结论就是：我们需要交换的是：8， 4.
TreeNode *first; TreeNode *second; TreeNode *pre; void inOrder(TreeNode *root){ if (root==NULL){return;} else{ inOrder(root->left); if (pre == NULL){pre = root;} else { if (pre->val > root->val){ if (first==NULL) {first = pre;} second = root; } pre = root; } inOrder(root->right); } } void recoverTree(TreeNode *root) { pre = NULL; first = NULL; second= NULL; inOrder(root); int val; val = first->val; first->val=second->val; second->val=val; return; }X. Iterative Version:
https://discuss.leetcode.com/topic/24975/java-solution-with-in-order-traversal/2
public void recoverTree(TreeNode root) {
if (root == null)
return;
Stack<TreeNode> stack = new Stack<TreeNode> ();
List<TreeNode> violates = new ArrayList<TreeNode> ();
TreeNode pre = null;
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else{
cur = stack.pop();
if (pre != null && cur.val < pre.val) {
if (violates.size() == 0) {
violates.add(pre);
violates.add(cur);
} else{
violates.set(1, cur);
}
}
pre = cur;
cur = cur.right;
}
}
if (violates.size() != 0) {
int temp = violates.get(0).val;
violates.get(0).val = violates.get(1).val;
violates.get(1).val = temp;
}
}1 public void recoverTree1(TreeNode root) { 2 if (root == null) { 3 return; 4 } 5 6 TreeNode node1 = null; 7 TreeNode node2 = null; 9 TreeNode pre = null; 10 11 Stack<TreeNode> s = new Stack<TreeNode>(); 12 TreeNode cur = root; 13 14 while (true) { 15 while (cur != null) { 16 s.push(cur); 17 cur = cur.left; 18 } 19 20 if (s.isEmpty()) { 21 break; 22 } 23 24 TreeNode node = s.pop(); 25 26 if (pre != null) { 27 // invalid order 28 if (pre.val > node.val) { 29 if (node1 == null) { 30 node1 = pre; 31 node2 = node; 32 } else { 33 node2 = node; 34 } 35 } 36 } 38 pre = node; 40 cur = node.right; 41 } 43 int tmp = node1.val; 44 node1.val = node2.val; 45 node2.val = tmp; 47 return; 48 }
X. O(nlogn)
https://discuss.leetcode.com/topic/29297/18ms-java-solution-with-in-order-traversal-and-sorting-o-nlogn-time-and-o-n-space
public void recoverTree(TreeNode root) {
// in-order traversal of treenodes, followed by sorting and reassignment of values
List<TreeNode> inorder = inorder(root);
List<Integer> inorderNumbers = new ArrayList<Integer>();
for (TreeNode node : inorder) {
inorderNumbers.add(node.val);
}
inorderNumbers.sort(null);
for (int i = 0; i < inorder.size(); i++) {
inorder.get(i).val = inorderNumbers.get(i);
}
}
private List<TreeNode> inorder (TreeNode root) {
List<TreeNode> result = new ArrayList<TreeNode>();
if (root == null) {
return result;
}
result.addAll(inorder(root.left));
result.add(root);
result.addAll(inorder(root.right));
return result;
}X. Using Morris traverse:
To find out the bad nodes, we have to perform an inorder traversal. So the question becomes: Can we conduct an inorder traversal with constant space usage?
Morris Traversal, that implement inorder traversal without recursion or stack.
http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/
The Morris traverse is like the following.
Firstly, take the root node as current node.
Then there are two possibilities.
- If current node doesn’t have left child, output the value. And current = current.right.
- If current node has left child, try to find the precursor node of current node, which is the right-most node of the left child of current. If the right child of it is null (If we don’t modify the tree, it should be null), set current as its right child, and current = current.left. Otherwise (It means that we have modify the tree and we have traverse all nodes in the left subtree of current node), set it to null, output current. And current = current.right.
During the traverse, we can find the nodes which are needed to be swapped.
But what about the time complexity? In fact, we only visit every edge twice. One is for going to that node, and another one is for searching the precursor node. There are only edges in a tree. So the time complexity is also .
The Morris traverse can also be used in pre-order and post-order traverse. There is a great article, including the detail pictures. You can visit http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html if you are interested.
public void recoverTree(TreeNode root) {
TreeNode current = root;
TreeNode prev = null;
TreeNode node1 = null;
TreeNode node2 = null;
while (current != null) {
if (current.left == null) {
if (prev != null) {
if (prev.val >= current.val) {
if (node1 == null)
node1 = prev;
node2 = current;
}
}
prev = current;
current = current.right;
} else {
TreeNode t = current.left;
while (t.right != null && t.right != current)
t = t.right;
if (t.right == null) {
t.right = current;
current = current.left;
} else {
t.right = null;
if (prev != null) {
if (prev.val >= current.val) {
if (node1 == null)
node1 = prev;
node2 = current;
}
}
prev = current;
current = current.right;
}
}
}
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}
Morris Traversal中序遍历的原理比较简单：
- 如果当前节点的左孩子为空，则输出当前节点并将其有孩子作为当前节点。
- 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点，也就是当前节点左子树的最右边的那个节点。
- 如果前驱节点的右孩子为空，则将它的右孩子设置为当前节点，当前节点更新为其左孩子。
- 如果前驱节点的右孩子为当前节点，则将前驱节点的右孩子设为空，输出当前节点，当前节点更新为其右孩子。
重复上述过程，直到当前节点为空，递归的时候我们同时需要记录错误的节点。那么我们如何知道一个节点的数据是不是有问题呢？对于中序遍历来说，假设当前节点为cur，它的前驱节点为pre，如果cur的值小于pre的值，那么cur和pre里面的数据就是交换的了。
Read full article from Yu's Coding Garden : leetcode Question 75: Recover Binary Search Tree