二叉搜索树的Morris中序遍历(O(1)空间)思路

关于二叉树的遍历，使用栈递归或者仿栈循环都是需要O(N)的空间，Morris Traversal保证了空间为O(1)，时间还是O(N)（比原来多了一遍）。
这里只介绍inOrder顺序。
思路：
对每一个cur节点，优先找到一个pre节点，这个pre节点的作用是，当后续cur节点遍历 到这个位置时，可以直接通过这个pre节点返回它需要返回的位置。
例如：
6
/ \
4 8
/ \
2 5

上面当cur节点在6的时候，pre节点会在5，因为后面当cur节点遍历到5的时候，可以通过pre节点直接返回6

当cur节点再4的时候，pre节点会在2，当后面cur到2的时候，可以直接返回4

pre找到了，是通过什么返回呢，因为不能修改二叉树结构，也不能使用堆栈记录。
通过mirror(镜像)，也就是说，当找到pre的时候（每个pre的右节点确保为null），在它的右节点创建一个镜像节点，这个镜像节点直接指向当前的cur节点。
这个操作是不占用空间的，因为只是互相引用。
例如：当上面的cur为6，pre为5，那么设置pre.right=cur，感觉上是这样：
6
/ \
4 8
/ \
2 5
\
6
/ \
4 8
…
其实并没有多出来那一块，只是5引用到6罢了
6
/ ↑ \
4 ↑ 8
/ \↑
2 5

理解了这些，那么后续就简单了，当cur遍历到pre的时候并且打印后，将pre新增的引用删除恢复原来的树便可。
代码：
function morrisTraversal(root){
let cur=root,pre
while(cur!=null){
// 当左为空，直接打印
if(cur.left==null){
console.log(cur.val)
cur=cur.right
}else{
// 当左不为空，先去找 pre
pre=cur.left
while(pre.right!=null && pre.right!==cur){
pre=pre.right
}
// 建立引用，用于返回
if(pre.right==null){
pre.right=cur
cur=cur.left
}else{
// 删除引用
console.log(cur.val)
pre.right=null
cur=cur.right
}
}
}
}