Morris遍历
概述
- Morris遍历：一种遍历二叉树的方式，并且时间复杂度O(N)，空间复杂度O(1)
- 常规的遍历无论递归还是非递归，空间复杂度都达不到常数级别（二叉树的高度 O(logN)）。Morris遍历，通过利用原树中的大量空闲指针的方式，达到节省空间的目地
- morris遍历的实现原则
记作当前节点为cur。
1 如果cur无左孩子，cur向右移动（cur=cur.right）
2 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
（1）如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
（2）如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）
3 cur为空时遍历结束 - Morris的应用：因为Morris遍历解决了最基本的遍历问题，所以很多二叉树的问题都可以使用Morris进行优化
实现思路
- cur：1，mostright：5；将5的右指针指向1，cur移动到2
- cur：2，mostright：4；将4的右指针指向2，cur移动到4
- cur：4，cur目前没有左孩子（不设置mostright），将cur移动到2
- cur：2，mostright：4；将4的右指针指向null，cur移动到5
- cur：5，cur无左孩子，将cur移动到1
- cur：1，mostright：5；将5的右指针指向null，cur移动到3
- cur：3，mostright：6，将6的右指针指向3，cur移动6
- cur：6，cur无左孩子，将cur移动到3
- cur：3，mostright：6；将6的右指针指向null，cur移动到7
- cur：7，cur无左孩子，将cur移动到null，遍历结束
Morris（cur）序列：1，2，4，2，5，1，3，6，3，7
可以发现：若节点有左孩子，会在Morris序列中出现2次，若无，就是一次
- 解析：
（1）常规的递归遍历方法，通过栈的数据结构记录头节点，实现树的遍历。每一个树的节点在整个遍历的过程中，都会经过三次
（2）Morris利用的是底层线索化，若存在左子树就是通过左子树最右的节点的右指针与头节点建立连系，即通过左子树的最右节点回到头节点。所以可以做到树的遍历，含左子树的节点经过两次，不含左子树的只经过一次
（3）如何判断节点是第几次访问：若访问该节点时mostRight.right = null，说明第一次访问，若mostRight.right = 当前节点，第二次访问
代码实现
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } public static void morris(Node head){ if (head == null){ return; } Node cur = head; //当前节点 Node mostRight = null; //左孩子的最右端 while (cur != null){ mostRight = cur.left; if (mostRight == null){ //无左子树 //只访问一次 cur = cur.right; } else { //cur存在左孩子 while (mostRight.right != null && mostRight.right != cur){ //找到最右端 //因为：mostRight.right可能以及进行了修改指向了头结点，要进行判断 mostRight = mostRight.right; } if (mostRight.right == null){ //将最右端的右指针与头节点相连 //第一次访问 mostRight.right = cur; //cur左移 cur = cur.left; } else { //mostRight.right == cur //第二次访问 mostRight.right = null; cur = cur.right; } } } }
使用Morris遍历得到前，中，后序序列
- 先序序列
1 只到达一次的节点直接打印
2 到达两次的只打印第一次
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } 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){ //无左子树 //只访问一次的节点直接打印 System.out.println(cur.value); cur = cur.right; } else { //cur存在左孩子 while (mostRight.right != null && mostRight.right != cur){ //找到最右端 //因为：mostRight.right可能以及进行了修改指向了头结点，要进行判断 mostRight = mostRight.right; } if (mostRight.right == null){ //将最右端的右指针与头节点相连 mostRight.right = cur; //cur第一次访问 System.out.println(cur.value); //cur左移 cur = cur.left; } else { //mostRight.right == cur; mostRight.right = null; //cur第二次访问，不进行操作 cur = cur.right; } } } }
- 中序遍历
1 只到达一次的节点直接打印
2 到达两次的只打印第二次
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } 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){ //无左子树 //只访问一次的节点直接打印 System.out.println(cur.value); cur = cur.right; } else { //cur存在左孩子 while (mostRight.right != null && mostRight.right != cur){ //找到最右端 //因为：mostRight.right可能以及进行了修改指向了头结点，要进行判断 mostRight = mostRight.right; } if (mostRight.right == null){ //将最右端的右指针与头节点相连 mostRight.right = cur; //cur第一次访问，不操作 //cur左移 cur = cur.left; } else { //mostRight.right == cur; mostRight.right = null; //cur第二次访问打印 System.out.println(cur.value); cur = cur.right; } } } }
- 后序遍历
1 第一次访问的不做任何操作
2 第二次访问时要求逆序打印左树的右边界
3 整个遍历结束后，逆序打印整个树的右边界
4 问题解决：任何逆序打印右边界，空间复杂度为O(1)，将右边界看为：节点只含右指针的单列表。将整个列表逆序，访问，再逆序恢复
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } 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){ //无左子树 //只访问一次的节点不操作 cur = cur.right; } else { //cur存在左孩子 while (mostRight.right != null && mostRight.right != cur){ //找到最右端 //因为：mostRight.right可能以及进行了修改指向了头结点，要进行判断 mostRight = mostRight.right; } if (mostRight.right == null){ //将最右端的右指针与头节点相连 mostRight.right = cur; //cur第一次访问，不操作 //cur左移 cur = cur.left; } else { //mostRight.right == cur; mostRight.right = null; //cur第二次访问逆序打印左子树的右边界 printEdge(cur.left); cur = cur.right; } } } //整个遍历结束后，打印整个树的右边界 printEdge(head); } public static void printEdge(Node x){ //打印X的右边界 Node temp = reverseEdge(x); //逆序后的头节点 Node cur = temp; while (cur != null){ //逆序打印 System.out.println(cur.value); cur = cur.right; } reverseEdge(temp); //再次逆序 } 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应用判断是否为BST
- 只需再中序遍历的打印位置进行修改即可，判断上一个值是否比当前值小
public static class Node{ int value; Node left; Node right; public Node(int date){ this.value = date; } } public static Boolean isBST(Node head){ if (head == null){ return true; } Node cur = head; //当前节点 Node mostRight = null; //左孩子的最右端 int preValue = Integer.MIN_VALUE; while (cur != null){ mostRight = cur.left; if (mostRight == null){ //无左子树 if (preValue < cur.value){ preValue = cur.value; }else { return false; } cur = cur.right; } else { //cur存在左孩子 while (mostRight.right != null && mostRight.right != cur){ //找到最右端 //因为：mostRight.right可能以及进行了修改指向了头结点，要进行判断 mostRight = mostRight.right; } if (mostRight.right == null){ //将最右端的右指针与头节点相连 mostRight.right = cur; //cur第一次访问，不操作 //cur左移 cur = cur.left; } else { //mostRight.right == cur; mostRight.right = null; if (preValue < cur.value){ preValue = cur.value; }else { return false; } cur = cur.right; } } } return true; }
