My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int index = 0;
public void recoverTree(TreeNode root) {
if (root == null)
return;
ArrayList<Integer> tracker = new ArrayList<Integer>();
in_order(root, tracker);
Collections.sort(tracker);
in_order_define(root, tracker);
return;
}
private void in_order(TreeNode root, ArrayList<Integer> tracker) {
if (root.left != null)
in_order(root.left, tracker);
tracker.add(root.val);
if (root.right != null)
in_order(root.right, tracker);
}
private void in_order_define(TreeNode root, ArrayList<Integer> tracker) {
if (root.left != null)
in_order_define(root.left, tracker);
root.val = tracker.get(index++);
if (root.right != null)
in_order_define(root.right, tracker);
return;
}
}
这道题目一开始想复杂了。觉得要交换结点。所以两个错误结点，还必须要把他们对应的两个父亲找出来。也就是四个结点，会很麻烦。
后来才明白，可以直接swap value rather than swapping nodes.
看了答案之后写出了最简单的一个版本。
复杂度是 O(n logn), 空间复杂度是 O(n)
后来看了 geekforgeeks 的改进版，
时间复杂度是O(n), 空间复杂度是 O(1)
自己重写了下。
关键在于， swap 错误，有几种类型。
有两种。
一种是， 错误的结点，在中序遍历中，正好相邻。
一种是，错误的结点，在中序遍历中，隔着好几个结点。
比如一棵树的中序遍历是，
3, 5, 7, 8, 10, 15, 20, 25
如果是错误1：
3, 25, 7, 8, 10, 15, 20, 5
如果是错误2
3, 5, 8, 7, 10, 15, 20, 25
那么我只需要找到一种方法，可以对这两种情况都可以处理，并且可以自我分别出，是哪个方法错误了。
方法如下，
设置四个指针：
first, second, third. 用来指示错误的结点。
prev，用来指示中序遍历中当前结点的上一个结点。
然后，碰到某个结点，当他， val < min，时，你就知道了，这里肯定有一个结点错误了。但错误类型你不清楚。可能是连着错，可能是后面还有个错的。
你先记录下来。
first = prev;
second = curr; // 当前结点
然后更新 min = curr.val;
prev = curr;
记住，min必须时刻更新至当前值，即使 curr.val < min
然后第二次如果又碰到一个 curr.val < min的化，
只用记录下这个结点，
third = curr;
如果没有，那就可能是之前连着错了。
结束中序遍历后，判断 third 是不是null。
如果不是，那么就表示是错误类型1.
于是直接交换 first, third
如果是，那就是错误类型2，
于是直接交换 first, second
参考网址如下：
http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
其实这道题目不是很难。但我一开始就想着，怎么swap node 而不是怎么 swap values
还有，这里我自己找出来的一个小技巧。
in-order 递归实现中，如果保存当前结点的上一个结点。
就是，
dfs(curr.left);
visit(curr);
prev = curr;
dfs(curr.right);
那么在先序遍历中是如何做得呢？
visit(curr);
prev = curr;
dfs(curr.left);
dfs(curr.right);
那么在后序遍历中是如何实现的呢？
dfs(curr.left);
dfs(curr.right);
visit(curr);
prev = curr;
发现规律没？
遍历的递归还是那么写， prev 一定是跟在 访问当前结点 visit(curr) 之后。
这几天效率真的不是很高。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode preNode = null;
private int pre = Integer.MIN_VALUE;
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode bigger = null;
TreeNode smaller = null;
int counter = 0;
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode p = root;
while (p != null) {
st.push(p);
p = p.left;
}
while (!st.isEmpty()) {
p = st.pop();
if (pre < p.val) {
pre = p.val;
preNode = p;
}
else {
pre = p.val;
counter++;
if (counter == 1) {
bigger = preNode;
smaller = p;
}
else if (counter == 2) {
smaller = p;
break;
}
}
if (p.right != null) {
p = p.right;
while (p != null) {
st.push(p);
p = p.left;
}
}
}
if (smaller == null || bigger == null) {
return;
}
else {
int temp = smaller.val;
smaller.val = bigger.val;
bigger.val = temp;
}
}
}
自己想出来的办法。
in order traversal, 然后维持两个指针，
当遇到 pre > curr.val的时候，就说明有错了。
第一次碰到的时候，记录下最大结点和最小结点
第二次碰到的时候，记录下最小结点
如果第二次没碰到，就直接交换第一次的最大结点和最小结点的value
否则，就交换第一次最大结点和第二次最小结点的value
思路是很清晰的。然后我中序遍历时间复杂度是 O(n),空间复杂度是 O(n)
题目要求空间复杂度是O(1)
pardon?
excuse me?
这是我活到现在，第一次知道，原来中序遍历是可以做到
time： O(n)
space: O(1)
Morris traversal
reference:
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
然后我自己又写了下，总时间快了 2ms
My code：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private TreeNode preNode = null;
private int preValue = Integer.MIN_VALUE;
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode bigger = null;
TreeNode smaller = null;
int counter = 0;
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) {
// visit
if (preValue < curr.val) {
preValue = curr.val;
preNode = curr;
}
else {
preValue = curr.val;
counter++;
if (counter == 1) {
bigger = preNode;
smaller = curr;
}
else {
smaller = curr;
}
}
curr = curr.right;
}
else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
}
else {
// visit
if (preValue < curr.val) {
preValue = curr.val;
preNode = curr;
}
else {
preValue = curr.val;
counter++;
if (counter == 1) {
bigger = preNode;
smaller = curr;
}
else {
smaller = curr;
}
}
pre.right = null;
curr = curr.right;
}
}
}
if (smaller == null || bigger == null) {
return;
}
else {
int temp = smaller.val;
smaller.val = bigger.val;
bigger.val = temp;
}
}
}
Anyway, Good luck, Richardo! -- 09/08/2016
