看答案做出来了，其实做的并不好，中间被各种cases虐。
思路其实并不难，in-order traversal是肯定的，顺序是从小到大。
当前应该比前一个大，如果cur < prev，说明prev有问题，那么发现第一个；
找第二个的时候有所不同，还是继续in-order往后走，一旦发现cur < prev，那cur有问题，而不是prev有问题。
第一次做写到这我觉得找到俩了，直接break(return)，然后发现不对。
有一种可能是检测某一个NODE的时候，实际上是prev和cur都有问题，需要他俩交换一下。
比如[1,2,3],从2回到1的时候，prev是2，cur是1，俩都有问题。所以在不满足sorted的情况下，更新第二个错误的node的时机是，只要第一个发现了第二个就必须，为了防止[1,2,3]的情况。
这里的问题是弄不好只有prev是错的，cur是对的。
比如[2,3,1]，从坐支3回到2的时候，出现问题，那么左支3(prev)肯定有问题，但是2是无辜的。。有问题的是2(cur)的右支1.
所以还要继续。。如果找不到不是sorted的了，那就是刚才的和node1一起更新的那个node2，找到了就是新更新的node2。
简而言之第二次找到不符合规定的才算数。。
做得并不好，修修补补看错误的test cases才改出来。 回想一下以前1刷2刷经常是这么修出个答案还觉得做出来了，唉。。
Time: O(n)
Space: O(n)
public class Solution {
TreeNode first = null;
TreeNode second = null;
TreeNode prev = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
return;
}
public void inOrder(TreeNode root) {
if (root == null) return;
inOrder(root.left);
if (prev != null && prev.val >= root.val) {
if (first == null) {
first = prev;
}
if (first != null) {
second = root;
}
}
prev = root;
inOrder(root.right);
}
}
迭代的大同小异，也是O(n)
真正意义上的Space O(1)其实是用Morris - traversal，然而第一次听说。
.....
........
研究了好久。
遍历左支的时候，找最右，然后连回root，每个SubTree都这样。。
看了代码不难理解，但是让我自己写估计要想好一会，先这样了。。二刷再说。
public class Solution {
public void recoverTree(TreeNode root) {
TreeNode prev = null;
TreeNode first = null;
TreeNode second = null;
TreeNode extra = null;
TreeNode temp = root;
while (temp != null) {
// out of order node detection part.
if (prev != null && temp.val <= prev.val) {
if (first == null) {
first = prev;
}
second = root;
}
// Morris
if (temp.left != null) {
extra = temp.left;
while(extra.right != null && extra.right != temp) {
extra = extra.right;
}
// going deep prcess is actaully hiding here...
if(extra.right == temp) {
extra.right = null;
prev = temp;
temp = temp.right;
}else{
extra.right = temp;
temp = temp.left;
}
// and here..
} else {
prev = temp;
temp = temp.right;
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}
Amazon OA2 做完还是没消息，神啊。。保佑我把，对我来说是救命的。。
二刷。
上午研究了一下Morris，找到这个题又来了一遍。
我是先写好了morris in-order traversal，然后再把比较添加进去。
代码里的 / / / / / visit / / / / /就是写traversal 的时候预留的actually visit node的地方。。然后在这些地方添加找错的代码。
不如一刷简单，一刷只有一个判断的位置，在WHILE LOOP开头，但是乍看之下觉得说不通。。
temp指针有三处移动的位置，我选择的2处是in-order的位置，另一处是pre order的位置，加在开始岂不是连pre order一起判断了么，顺序就不是sorted的了。。不知道怎么搞的。
不想了。。
public class Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null; // first messed up node
TreeNode second = null; // seond fucked up node
TreeNode prev = null; // previous pointer during traversal
TreeNode temp = root; // temp pointer during traversal
TreeNode tail = null; // tail pointer for morris traversal
while (temp != null) {
if (temp.left != null) {
tail = temp.left;
// find right most child && 2nd time we visit the node
while (tail.right != null && tail.right != temp) {
tail = tail.right;
}
// first time we are here
if (tail.right == null) {
tail.right = temp;
temp = temp.left;
} else {
// 2nd time we are here
tail.right = null;
////////// visit //////////
if (prev != null && temp.val <= prev.val) {
if (first == null) {
first = prev;
}
second = temp;
}
////////// visit //////////
prev = temp;
temp = temp.right;
}
} else {
/////////// visit /////////////
if (prev != null && temp.val <= prev.val) {
if (first == null) {
first = prev;
}
second = temp;
}
/////////// visit //////////
prev = temp;
temp = temp.right;
}
}
int tempVal = first.val;
first.val = second.val;
second.val = tempVal;
return;
}
}