这道题的难点在于，如何用O(1)的空间inorder traverse tree，利用到了Morris Algorithm,关键点要理解一个概念，前驱点，也就是一个点，他的左子节往右下探到底的点（为了方便在这里假设A点的前驱点是B，那么A成为B的被前驱点），这个点有个特性，就是如果在inorder的遍历中，这个点打印出来，就证明，被前驱点的左子树打完了，该打被前驱点，然后轮到被前驱点的右子树了。
我一开始有一个地方想了很久，那就是，Morris算法里，到底有哪几种类型的点可以被打印。答案是，只有两种！一种是前驱点，另一种是被前驱点，而且前驱点打完，马上打被前驱点，这是一个递推：
1：从一个根开始，找到这个根，最左最左的前驱点，也就是最左的点，开始打
2: 每打印完一个点，这个点都只可能有两种身份（如前所述），前驱点或者被前驱点。如果是前驱点，找到被前驱点，打印被前驱点，然后开始打他的右子树，重复步骤一，如果是被前驱点，直接打他的右子树，同样是重复步骤一，直到没有点可以打。
注意：这里有一个独特的点，就是没有左子树的点，他自己就是他自己的前驱点。
另外，还有一个小点要注意，每次找到一个B，他前面的是A，A>B,那么A一定是最终结果里的一个，B先留住，如果再次碰到了一组，C>D,只更新D，也就是说如果碰到了第二组，要换的是：D换B
Morris 算法详解： https://www.cnblogs.com/anniekim/archive/2013/06/15/morristraversal.html
代码：
class Solution {
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
public void recoverTree(TreeNode root) {
// predecessor is a Morris predecessor.
// In the 'loop' cases it could be equal to the node itself predecessor == root.
// pred is a 'true' predecessor,
// the previous node in the inorder traversal.
TreeNode x = null, y = null, pred = null, predecessor = null;
while (root != null) {
// If there is a left child
// then compute the predecessor.
// If there is no link predecessor.right = root --> set it.
// If there is a link predecessor.right = root --> break it.
if (root.left != null) {
// Predecessor node is one step left
// and then right till you can.
predecessor = root.left;
while (predecessor.right != null && predecessor.right != root)
predecessor = predecessor.right;
// set link predecessor.right = root
// and go to explore left subtree
if (predecessor.right == null) {
predecessor.right = root;
root = root.left;
}
// break link predecessor.right = root
// link is broken : time to change subtree and go right
else {
// check for the swapped nodes
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
}
pred = root;
predecessor.right = null;
root = root.right;
}
}
// If there is no left child
// then just go right.
else {
// check for the swapped nodes
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
}
pred = root;
root = root.right;
}
}
swap(x, y);
}
}
