package com.jiucaiyuan.net.question;
import com.jiucaiyuan.net.algrithm.tree.Node;
/**
* 【Morris遍历】
* 一种遍历二叉树的方式，时间复杂度是O(N)，额外空间复杂度是O(1)
* 通过利用原树中大量空闲指针的方式，达到节省空间的目的
* 遍历过程中，更改了底层叶子结点指针，完成遍历后，恢复了指针指向
*
* @Author jiucaiyuan 2022/5/10 22:45
* @mail services@jiucaiyuan.net
*/
public class Morris {
/**
* <pre>
* 【Morris遍历】
* 一种遍历二叉树的方式
* 通过利用原树中大量空闲指针的方式，达到节省空间的目的
* 二叉树的遍历算法
* 【Morris遍历细节】
* 假设来到当前节点curr，开始时curr来到头结点位置
* 1）如果curr没有左孩子，curr向右移动（curr=curr.right）
* 2）如果curr有左孩子，找到左子树上最右的节点mostRight:
* a.如果mostRight右指针指向null，让其指向curr，然后curr向左移动（curr = curr.left）
* b.如果mostRight右指针指向curr，让其指向null，然后curr向右移动（curr = curr.right）
* 3）curr为空时遍历停止
* 【复杂度分析】
* 时间复杂度是O(N)
* 额外空间复杂度是O(1)
* 节点有左子树，会访问两次，如果没有左子树，只访问一次
* </pre>
*
* @param head
*/
public static void morris(Node<Integer> head) {
if (head == null) {
return;
}
Node curr = head;
Node mostRight = null;
while (curr != null) {
System.out.print(curr.value + ","); //morris 遍历序
mostRight = curr.left;
if (mostRight != null) {
//最右指向不为空，且指向的不是自己，一直找左子树的最右节点
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
mostRight.right = curr;
curr = curr.left;
continue;
} else { //否则，右指针一定指向当前节点的（判断是第二次访问当前节点
mostRight.right = null;//恢复左子树最右侧节点的默认值
}
}
curr = curr.right;
}
}
/**
* morris遍历（前序遍历二叉树）
* 由morris遍历序改成先序遍历，morris遍历时
* 只访问一次的节点，直接打印
* 访问两次的节点，第一次打印
*
* @param head
*/
public static void morrisPre(Node head) {
if (head == null) {
return;
}
Node curr = head;
Node mostRight = null;
while (curr != null) {
mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
System.out.print(curr.value + ",");
mostRight.right = curr;
curr = curr.left;
continue;
} else {
mostRight.right = null;//恢复左子树最右侧节点的默认值
}
} else {
System.out.print(curr.value + ",");
}
curr = curr.right;
}
}
/**
* morris遍历（中序遍历二叉树）
*
* @param head
*/
public static void morrisMid(Node head) {
if (head == null) {
return;
}
Node curr = head;
Node mostRight = null;
while (curr != null) {
mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
mostRight.right = curr;
curr = curr.left;
continue;
} else {
System.out.print(curr.value + ",");
mostRight.right = null;//恢复左子树最右侧节点的默认值
}
} else {
System.out.print(curr.value + ",");
}
curr = curr.right;
}
}
/**
* morris遍历（中序遍历二叉树）
* 由morris遍历序改成中序遍历，morris遍历时
* 只访问一次的节点，直接打印
* 访问两次的节点，第二次打印
*
* @param head
*/
public static void morrisIn(Node head) {
if (head == null) {
return;
}
Node curr = head;
Node mostRight = null;
while (curr != null) {
mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
mostRight.right = curr;
curr = curr.left;
continue;
} else {
mostRight.right = null;//恢复左子树最右侧节点的默认值
}
}
System.out.print(curr.value + ",");
curr = curr.right;
}
}
/**
* morris遍历（后序遍历二叉树）
* 由morris遍历序改成中序遍历，morris遍历时
* 只访问一次的节点，不打印
* 访问两次的节点，第一次访问时，不打印
* 访问两次的节点，第二次访问时，逆序打印自己左树的右边界
* 最后再统一逆序打印整棵树的右边界
*
* @param head
*/
public static void morrisPost(Node head) {
if (head == null) {
return;
}
Node curr = head;
Node mostRight = null;
while (curr != null) {
mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
mostRight.right = curr;
curr = curr.left;
continue;
} else {
mostRight.right = null;//恢复左子树最右侧节点的默认值
printEdge(curr.left); //逆序打印自己左树的右边界
}
}
curr = curr.right;
}
printEdge(head); //逆序打印整棵树的右边界
System.out.println();
}
/**
* 逆序打印x为头结点的二叉树右边界
*
* @param x
*/
public static void printEdge(Node<Integer> x) {
Node<Integer> tail = reverseEdge(x);
Node<Integer> curr = tail;
while (curr != null) {
System.out.println(curr.value + " ");
curr = curr.right;
}
reverseEdge(tail);
}
/**
* 把from——>from.right——>from.right.right单链表逆序
*
* @param from
* @return 逆序后的头结点
*/
public static Node<Integer> reverseEdge(Node<Integer> from) {
Node<Integer> pre = null;
Node<Integer> next = null;
while (from != null) {
next = from.right;
from.right = pre;
pre = from;
from = next;
}
return pre;
}
/**
* morris遍历的应用
* 判断一颗二叉树是否是搜索二叉树
* （中序遍历时，遍历序列是升序的，即，左子树都比自己小，右子树都比自己大）
* 时间复杂度 O(N)
* 空间复杂度 O(1)
*
* @param head
*/
public static boolean isBST(Node<Integer> head) {
if (head == null) {
return true;
}
Node<Integer> curr = head;
Node mostRight = null;
int preValue = Integer.MIN_VALUE;
while (curr != null) {
mostRight = curr.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != curr) {
mostRight = mostRight.right;
}
//截止到这里，mostRigt找到了左子树的最右侧节点
if (mostRight.right == null) { //第一次访问最右侧节点
mostRight.right = curr;
curr = curr.left;
continue;
} else {
mostRight.right = null;//恢复左子树最右侧节点的默认值
}
}
// System.out.print(curr.value + ",");
//原本中序遍历打印的位置，做比较即可
if (preValue >= curr.value) {
return false;
}
curr = curr.right;
}
return true;
}
public static void main(String[] args) {
Node head = new Node(1);
Node left = new Node(2);
Node right = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
head.left = left;
head.right = right;
left.left = node4;
left.right = node5;
right.left = node6;
right.right = node7;
morris(head);
System.out.println();
System.out.println("---------------------------");
morrisPre(head);
System.out.println();
System.out.println("---------------------------");
morrisMid(head);
System.out.println();
System.out.println("---------------------------");
morrisIn(head);
}
}