Moriis 遍历
Morris 遍历是二叉树遍历的一种方式，传统的递归和非递归遍历的时间复杂的都是O(N)，空间复杂度都是O(h)（h为树的高度），而 Morris 遍历可以做到时间复杂的依然为 O(N) 的情况下，空间复杂度降到 O(1)。
Morris 遍历的实现原理
定义一个 cur 节点，指向 root 节点：
- 当 cur.left == null 时，cur 向右移动 cur = cur.right
- 当 cur.left != null 时，找到 cur 左子树的最右的节点 mostRight
- 当 mostRight 右指针为空时，修改 mostRight 右指针指向 cur，cur 向左移动，cur = cur.left
- 当 mostRight 右指针指向 cur 时，修改 mostRight 右指针指向 null，cur 向右移动
- cur == null 停止。
cur 依次来到节点的顺序我们称之为 Moriis 序。我们来看下面的图片：
从 Morris 序中我们可以发现：
任何节点如果其有左孩子一定会在 Moriis 序中出现两次，为什么改动左子树最右节点的右指针的走向，为了确认是第一次来到当前节点还是第二次来到当前节点，左子树最右节点右指针指向空表示第一次来到当前节点，指向自己则说明第二次来。
Morris 遍历代码实现
我们观察上面示例的 Morris 序：1，2，4，2，5，1，3，6，3，7 可以发现：
拥有左子树的节点1，2，3都出现了两次，
所以我们看只打印第一次出现的节点，次序为 1，2，4，5，3，6，7是不是发现这就是先序遍历了呢。
我们在尝试让其打印出现两次的节点的第二次，只出现一次的直接打印，顺序为 4，2，5，1，6，3，7是不是发现这就是中序遍历了呢。
要实现后序遍历有一点繁琐， 打印时机就在能回到自己两次且第二次回到自己的时候，但并非打印他自己 ，而是逆序打印它的左树右边界（二叉树的边界：左边界的定义是从根到最左侧结点的路径。 右边界的定义是从根到最右侧结点的路径。 若根没有左子树或右子树，则根自身就是左边界或右边界。）， 然后再单独逆序打印整棵树的右边界，来用上面的示例模拟一下过程：
- 当第二次回到2时，此时 cur 的左树右边界为4，逆序打印4
- 当第二次回到1时，此时 cur 的左树右边界为2 –> 5，逆序打印后4，5，2
- 当第二次回到3时，此时 cur 的左树右边界为6，逆序打印后4，5，2，6
- 最后单独逆序打印整棵树的右边界，打印后 4，5，2，6，7，3，1为后序遍历的结果。
代码实现：
中序遍历：
public static void morrisIn(TreeNode root) {
if(root == null) {
return;
}
TreeNode cur = root;
TreeNode mostRight = null;
while(cur != null) {
mostRight = cur.left; //cur的左子树
if(mostRight != null) { //左子树不为空
//mostRight.right==null --> 找到左子树最右节点（第一次）
//mostRight.right != cur --> 找到左子树最右节点（第二次）
while(mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}//从while中出来就表示找到左子树最右节点为mostRight
if(mostRight.right == null) { //第一次到达
mostRight.right = cur; //修改mostRight右指针指向当前节点
cur = cur.left; //当前节点cur左移
continue;
} else { //mostRight.right == cur
mostRight.right = null; //当前节点第二次被访问，修改mostRight右指针指向null
}
}
System.out.println(cur.val + " "); //中序遍历
cur = cur.right; //cur.left == null(左子树为空) || mostRight.right != cur 此时都需要右移
}
}
先序遍历
public static void morrisPre(TreeNode root) {
if(root == null) {
return;
}
TreeNode cur = root;
TreeNode mostRight = null;
while(cur != null) {
mostRight = cur.left; //cur的左子树
if(mostRight != null) { //左子树不为空
//mostRight.right==null --> 找到左子树最右节点（第一次）
//mostRight.right != cur --> 找到左子树最右节点（第二次）
while(mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}//从while中出来就表示找到左子树最右节点为mostRight
if(mostRight.right == null) { //第一次到达
mostRight.right = cur; //修改mostRight右指针指向当前节点
System.out.println(cur.val); //先序遍历
cur = cur.left; //当前节点cur左移
continue;
} else { //mostRight.right != cur
mostRight.right = null; //当前节点第二次被访问，修改mostRight右指针指向null
}
}
else {
System.out.println(cur.val); //先序遍历
}
cur = cur.right; //cur.left == null(左子树为空) || mostRight.right != cur 此时都需要右移
}
}
后续遍历：
public static void morrisPos(TreeNode root) {
if(root == null){
return;
}
TreeNode cur = root;
TreeNode 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(root); //打印整棵树的左树右边界
System.out.println();
}
public static void printEdge(TreeNode node){
TreeNode tail =reverseEdge(node);
TreeNode cur = tail;
while (cur != null ){
System.out.print(cur.value+" ");
cur =cur.right;
}
reverseEdge(tail);
}
public static TreeNode reverseEdge(TreeNode node){
Node pre = null;
Node next = null;
while (node != null){
next = node.right;
node.right = pre;
pre = node;
node = next;
}
return pre;
}
Original: https://www.cnblogs.com/leeleezl/p/16216963.html
Author: 栗子leeleezl
Title: Moriis神级遍历！
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588413/
转载文章受原作者版权保护。转载请注明原作者出处！