时间复杂度:O(N)
空间复杂度:O(1)
具体流程:
假设当前来到的节点记为cur
- 如果cur无左孩子,cur向右移动(cur=cur.right)
- 如果cur有左孩子,找到cur左子树的最右节点,记为mostright:
- 如果mostright的右指针指向空,让其指向cur,cur向左移动(cur=cur.left)
- 如果mostright的右指针指向cur,让其指向空,cur向右移动(cur=cur.right)
中序遍历,在最后一次到达该节点时打印
public static void morrisIn(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 = cur
mostRight.right = null;
}
}
System.out.print(cur.value + " ");
cur = cur.right;
}
System.out.println();
}
先序遍历:在第一次到达该节点时打印
public static 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 = cur
mostRight.right = null;
}
} else {
System.out.print(cur.value + " "); // 第一次来到这个节点
}
cur = cur.right;
}
System.out.println();
}
后序遍历:只关注能到达2次的节点,在第二次到达该节点时,逆序打印左子树右边界。最后打印整棵树的右边界。
逆序打印实现:类似反转链表打印后再恢复原样