基本概念
Morris 遍历：时间复杂度O(N)、额外空间复杂度O(1)，N 为二叉树的节点个数。

说明：和二叉树的遍历有关的最优解都是Morris 遍历。



分析：
Morris 遍历：对于有左子树的节点current，会遍历到两次，否则只会遍历到一次。对于有左子树的节点，它会先让左子树的最右节点 rightmost指向它，从而达到之后能从底层节点返回上层。



如果 rightmost的右指针为空，说明是第一次到达current，然后会让它指向current；

如果 rightmost的右指针指向current ，说明这是第二次到达current，current的左子树已经遍历完了，该回到current，开始遍历其右子树了。

具体步骤：


1、如果current 无左子树，current 向右移动【遍历其右子树】【无左子树，current 只会经过一次】；



2、如果current 有左子树，找到current 左子树上最右的节点 rightmost：



2.1、若 rightmost的右指针指向null【说明这是第一次来到current 】，让 rightmost的右指针指向current 【那么之后就可以通过该指针返回current 了】，current 向左移动【遍历左子树】；



2.2、若 rightmost的右指针指向的是current 【说明这是第二次来到current，current 的左子树已经遍历完了】，让 rightmost的右指针指向空，current 向右移动。



说明：

传统的二叉树遍历要么是自己实现一个栈要么借助系统栈作为辅助空间，都是为了解决底层节点怎么回到最上层。Morris 遍历利用特殊节点的指针解决了这一个问题，因此比较省空间。

核心 代码


private static void morris(Node node){
Node current = node,rightmost = null;
while(current != null){
rightmost = current.left;
if(rightmost != null){
while(rightmost.right != null && rightmost.right != current)
rightmost = rightmost.right;
if(rightmost.right == null){
rightmost.right = current;
current = current.left;
continue;
}else rightmost.right = null;
}
current = current.right;
}
}