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?
constant space resolution: Morris Traversal or Morris Threading Traversal.
也是用中序遍历的思想，找那个元素不是递增。Morris traversal用threaded binary tree进行中序遍历，只要Ｏ(1)的空间复杂度。
/**
* 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 cur = root, prev = null, n1 = null, n2 = null, last = null;
while (cur != null) {
prev = cur.left;
if (prev == null) { // visit current node
if (last != null && cur.val < last.val) {
if (n1 == null) {
n1 = last;
n2 = cur;
} else {
n2 = cur;
}
}
last = cur;
cur = cur.right; // jump to its next
continue;
}
while (true) {
if (prev.right == null) {
prev.right = cur;
cur = cur.left;
break;
} else if (prev.right == cur) { // visit current node
prev.right = null;
if (cur.val < last.val) {
if (n1 == null) {
n1 = last;
n2 = cur;
} else {
n2 = cur;
}
}
last = cur;
cur = cur.right;
break;
}
prev = prev.right;
}
}
int tmp = n1.val;
n1.val = n2.val;
n2.val = tmp;
}
}
只会straight forward的Ｏ（n)解法：ＢＳＴ的中序遍历应该是递增的，对给的树中序遍历，如果碰到递减的元素，记下来，说明是被交换过的。
/**
* 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) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode n1 = null, n2 = null, n3 = null, cur = root, prev = null, tmp = null;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
while (!stack.empty()) {
cur = stack.pop();
if (prev != null && cur.val < prev.val) {
if (n1 == null) {
n1 = prev;
n2 = cur;
} else {
n2 = cur;
break;
}
}
prev = cur;
tmp = cur.right;
while (tmp != null) {
stack.push(tmp);
tmp = tmp.left;
}
}
// should find the parent of n1 and n2 instead of swapping values？
int v1 = n1.val;
n1.val = n2.val;
n2.val = v1;
}
}