二叉树前中后序的递归和非递归实现时间复杂度O(N)，额外空间复杂度O(h),h是树高度。如果树很棒状那么O(h)接近O(N),而Morris遍历可以做到额外空间复杂度O(1)，即只用有限几个变量实现。
Morris遍历过程如下图所示，节选自左程云算法提高班
下面是一个Morris遍历的具体实例，图中cur依次来到的节点顺序即该实例的Morris序，图源链接如右：链接
Morris遍历流程：若节点无左树，那么只来到这个节点一次；若节点有左树，那么来到这个节点两次。对于有左树的节点，在第一次到该节点之后和第二次到该节点之前，把该节点所有的子树遍历完。
Morris遍历实质：利用底层节点右指针指向这件事情，方便回到上级节点。二叉树结构天然的缺陷是没有往上指的指针，只有往下指的指针，所以完成遍历的话势必要建立一种机制回到上级去，因为要求仅使用有限几个变量，所以如果不是用现成的栈结构的话，就只能从底层的空闲指针入手了。上面提到对于有左树的节点，按照Morris序遍历会来到两次，那么对于有左子树的节点如何知道是第一次来到这个节点还是第二次来到这个节点？如果节点左子树最右节点指向空，第一次来到；如果节点发现左子树最右节点指向自己，第二次来到；即利用左子树上最右节点的右指针走向来标记是第一次来到自己还是第二次来到自己。
Morris遍历其实在高度的模仿递归序，但只能做到没左子树的节点来到一次，有左子树的节点来到两次，无论如何到不了一个节点三次，在递归里你总是知道是第几次来到当前节点，因为跑到哪一行你总知道，系统栈会告诉你现在在第几行，会告诉你之前跑过什么，接着这个过程继续往下跑就行，利用系统栈的机制告诉你是第几次来到当前节点，Morris遍历没这种机制，也不能记录任何状态，只能用左子树最右节点的右指针指向来标记这件事。
Morris遍历代码：
public static class Node {
public int value;
Node left;
Node right;
public Node(int data) {
this.value = data;
}
}
public static void morris(Node head) {
if (head == null) {
return;
}
Node cur = head;
Node mostRight = null;
while (cur != null) { // 过流程
mostRight = cur.left; // mostRight是cur左孩子
if (mostRight != null) { // 有左子树
//因为我们会人为改写最右节点的右指针，所以是两个判断条件
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
// mostRight变成了cur左子树上，最右的节点
if (mostRight.right == null) { // 这是第一次来到cur
mostRight.right = cur;
cur = cur.left;
continue;
} else { // mostRight.right == cur 第二次
mostRight.right = null;
}
}
cur = cur.right;
}
}
Morris遍历改先序：来到一次的节点直接打印，来到两次的节点第一次到达该节点时打印，代码如下：
public static void morrisPre(Node head) {
if (head == null) {
return;
}
Node cur = head;
Node mostRight = null;
while (cur != null) { // 过流程
mostRight = cur.left; // mostRight是cur左孩子
if (mostRight != null) { // 有左子树
//因为我们会人为改写最右节点的右指针，所以是两个判断条件
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
// mostRight变成了cur左子树上，最右的节点
if (mostRight.right == null) { // 这是第一次来到cur
System.out.println(cur.value);//打印
mostRight.right = cur;
cur = cur.left;
continue;
} else { // mostRight.right == cur 第二次
mostRight.right = null;
}
} else { // 没有左子树的情况
System.out.println(cur.value);//打印
}
cur = cur.right;
}
}
Morris遍历改中序：来到一次的节点直接打印，来到两次的节点第二次到达该节点时打印，代码如下：
public static void morrisIn(Node head) {
if (head == null) {
return;
}
Node cur = head;
Node mostRight = null;
while (cur != null) { // 过流程
mostRight = cur.left; // mostRight是cur左孩子
if (mostRight != null) { // 有左子树
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
// mostRight变成了cur左子树上，最右的节点
if (mostRight.right == null) { // 这是第一次来到cur
mostRight.right = cur;
cur = cur.left;
continue;
} else { // mostRight.right == cur
mostRight.right = null;
//注释1
}
}
//此处是打印只来到1次的节点，注释1处是打印来到2次且第2次来到的节点；
//但注释1处打印行为可以写到这里，效果是一样的，2个打印行为即合并为1个
System.out.println(cur.value);
cur = cur.right;
}
}
Morris遍历改后序：
处理时机：能回到自己两次的节点且是第二次回到一个节点的时候
如何处理：遍历阶段逆序打印左子树右边界，遍历完成后，单独逆序打印整棵树右边界
代码如下：
public static void morrisPos(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;
printEdge(cur.left);
}
}
cur = cur.right;
}
//最后打印整棵树的右边界
printEdge(head);
System.out.println();
}
// 以X为头的树，逆序打印这棵树的右边界
public static void printEdge(Node X) {
Node tail = reverseEdge(X);
Node cur = tail;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.right;
}
reverseEdge(tail);
}
//从from开始，只关心right指针，并且认为right指针就是单链表的next指针，请把这个单链表逆序
public static Node reverseEdge(Node from) {
Node pre = null;
Node next = null;
while (from != null) {
next = from.right;
from.right = pre;
pre = from;
from = next;
}
return pre;
}
Morris遍历应用：如何判断一棵树是搜索二叉树？经典做法是中序遍历该树并看是不是升序的，现在用Morris遍历每次打印节点时看前一个打印的节点是不是比当前打印的节点小即可，原本额外空间复杂度O(h),现在额外空间复杂度O(1)，一切遍历问题都可以以Morris遍历作为最优解。
网友评论