BiruLyu
8/3/2017 - 4:50 AM

## 99. Recover Binary Search Tree(#Morris).java

``````public class Solution {

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);
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null, second = null;
TreeNode cur = root, pre = null;
while (cur != null) {
if (cur.left == null) {

if (pre != null && pre.val > cur.val) {
if (first == null) {
first = pre;
second = cur;
} else {
second = cur;
}
}
pre = cur;
cur = cur.right;
} else {
TreeNode temp = cur.left;
while (temp.right != null && temp.right != cur) {
temp = temp.right;
}
if (temp.right == null) {
temp.right = cur;
//pre = cur;
cur = cur.left;
} else {

if (pre != null && pre.val > cur.val) {
if (first == null) {
first = pre;
second = cur;
} else {
second = cur;
}
}
temp.right = null;
pre = cur;
cur = cur.right;
}

}
}

// swap two node values;
if(first!= null && second != null){
int t = first.val;
first.val = second.val;
second.val = t;
}
}
}``````