Morris算法进行二叉树遍历
二叉树作为计算机中的一个重要数据结构，在很多领域都会涉及到，而提到二叉树，我们首先想到的就是其3种遍历方式--前序、中序和后序，对于这三种遍历方式，我们很容易通过使用递归或者迭代的方式实现，时间复杂度为O(N)。但是这两种实现方式都需要使用堆栈进行节点信息的存储，即空间复杂度也是O(N)。
但是还有一种更为巧妙的遍历方法Morris算法，该算法的时间复杂度也是O(N)，但是空间复杂度却能达到最优的O(1)。下面根据二叉树的三种遍历方式详细介绍Morris算法。
解决问题思路
1.初始化当前节点为current,一开始current来到整树头.
2.当前节点不为空:
(1)当前节点没有左孩子,currrent=current->right
(2)当前节点有左孩子,找到当前左子树的最右节点，记为mostright
- (a)如果mostright的right指针指向空(NULL)，让其指向cur(mostright.right=cur)，cur向左移动（cur=cur.left）
- (b)如果mostright的right指针指向cur，让其指向空(mostright.right=null)，cur向右移动（cur=cur.right）
根据需要的遍历顺序在不同的时机打印节点,后续遍历时需要返回转列表进行遍历.
- 初始化当前节点为current,一开始current来到整树头
初始化当前节点为current,一开始current来到整树头
image-20210627204036975
image-20210627204308739
image-20210627204534365
image-20210627204851911
image-20210627205157672
image-20210627205444942
image-20210627205740275
image-20210627205922167
image-20210627210122865
image-20210627210405872
Morris序，节点有左孩子，来到两次
image-20210627210900278
时间复杂度为O(N)，空间复杂度为O(1)。因为递归遍历二叉树会产生一个O(h)的递归栈的空间复杂度；要是用非递归使用栈来实现也是要产生一个O(h)的空间复杂度。所以morris遍历在二叉树遍历算是神级一般的算法了。
基础节点Code
public static class Node {
public int value;
Node left;
Node right;
public Node(int data) {
this.value = data;
}
}
Morris遍历Code
public static void morris(Node head) {
if (head == null) {
return;
}
Node cur = head;
Node mostRight = null;
while (cur != null) {//cur==null 循环结束
// cur有没有左树
mostRight = cur.left;
if (mostRight != null) { // 有左树的情况下
// 找到cur左树上，真实的最右
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;//找到当前左子树的最右节点，记为mostright
}
// 从while中出来，mostRight一定是cur左树上的最右节点
// mostRight
if (mostRight.right == null) {//如果mostright的right指针指向空(NULL)
mostRight.right = cur;//让其指向cur(mostright.right=cur)
cur = cur.left;//cur向左移动,（cur=cur.left）
continue;
} else { // mostRight.right != null -> mostRight.right == cur
mostRight.right = null;
}
}
cur = cur.right;//(1)当前节点没有左孩子,currrent=current->right
}
}
前序遍历：
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) {
System.out.print(cur.value + " ");
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
System.out.print(cur.value + " ");
}
cur = cur.right;
}
System.out.println();
}
中序遍历：
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 = null;
}
}
System.out.print(cur.value + " ");
cur = cur.right;
}
System.out.println();
}
后续遍历:
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();
}
Morris遍历判断是否搜索二叉树
public static boolean isBST(Node head) {
if (head == null) {
return true;
}
Node cur = head;
Node mostRight = null;
Integer pre = null;
boolean ans = true;
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;
}
}
if (pre != null && pre >= cur.value) {//中序遍历值比较
ans = false;
}
pre = cur.value;
cur = cur.right;
}
return ans;
}
网友评论