二叉树递归遍历的实质是，只要这个节点不为空，那么这个节点一定会遍历3次，先序中序后续只不过是打印的时机不同。先序是第一次到达这个节点，中序是第二次，后序是第三次。Morris遍历高度模仿这个过程。Morris遍历，如果这个节点有左子树，那么能到达这个节点两次，没有左子树，只能到达这个节点一次。Morris遍历的时间复杂度为O(n)，空间复杂度为O(1)。
morris.jpg
Morris遍历的规则如下
- 来到的当前节点记为cur（引用）， 如果cur无左孩子，cur向右移动，cur = cur.right。
- 如果cur有左孩子，找到cur左子树最右的节点，记作mostRight
1）如果mostRight的right指针指向空，让其指向cur，cur向左移动
（cur = cur.left）。
2）如果mostRight的right指针指向cur，让其指向空，cur向右移动。
然后，值得注意的是，Morris遍历可以写成二叉树的先中后，相关的方法会在代码中注释
public class MorrisTraversal {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
//morris遍历
public void morris(Node head){
if(head == null)
return;
Node cur = head;
Node mostRight = null;
while(cur != null){
mostRight = cur.left;
//左孩子不为空的情况
if(mostRight != null){
//找到最右的节点
while(mostRight.right != null && mostRight.right != cur)
mostRight = mostRight.right;
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;
}else {
mostRight.right = null;
}
}
System.out.print(cur.value + " ");
cur = cur.right; //左孩子为空，直接向右移动
}
System.out.println();
}
//Morris前序遍历
public void morrisPre(Node head){
if(head == null)
return;
Node cur = head;
Node mostRight = null;
while(cur != null){
mostRight = cur.left;
//左孩子不为空的情况
if(mostRight != null){
//找到最右的节点
while(mostRight.right != null && mostRight.right != cur)
mostRight = mostRight.right;
if(mostRight.right == null){
mostRight.right = cur;
System.out.print(cur.value + " ");
cur = cur.left;
continue;
}else {
mostRight.right = null;
}
}else {
System.out.print(cur.value + " ");
}
cur = cur.right; //左孩子为空，直接向右移动
}
System.out.println();
}
//后面的太复杂了，暂时先放着。。。
//Morris中序遍历
//Morris后续遍历
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(2);
head.right = new Node(6);
head.left.left = new Node(1);
head.left.right = new Node(3);
head.right.left = new Node(5);
head.right.right = new Node(7);
new MorrisTraversal().morris(head);
}
}
