Morris traversal
Morris traversal is used to save space when traversing binary trees
If it is a conventional binary tree traversal, whether it is implemented recursively or iteratively, the space complexity is O(M), M is the height of the tree, because each node will return to it three times, the difference in the order of traversal is here Which of the three visits to this node
// the first time
process(node.left)
// the second time
process(node.right)
// the third time
Therefore, there is a need to store the current node, and pop it from the stack when returning to the current node
How many nodes will be pushed into the stack, and the height of the tree determines
Morris traversal is a space-complex optimization of binary tree traversal.
Details of the Morris Traversal
Morris traversal is to use the free right pointer of the node in the tree
Suppose you come to the current node cur, at the beginning cur comes to the position of the head node
1) If cur has no left child, cur moves to the right (cur = cur.right)
2) If cur has a left child, find the rightmost node mostRight on the left subtree
a. If the right pointer of mostRight points to null, let it point to cur, and then move cur to the left (cur = cur.left)
b. If the right pointer of mostRight points to cur, let it point to null, then cur moves to the right (cur = cur.right)
3) When cur is empty, the traversal stops
In fact, it uses the right pointer state of the rightmost node of the left subtree of the current node to mark how many times it has come to the current node
If the right pointer of the rightmost node of the left subtree of the current node is null, it means that it is the first time to come to the current node
If the right pointer of the rightmost node of the left subtree of the current node points to the current node, it means that it has been here once before, and now it is the second time to come to the current node
Morris traversal code implementation
/**
* Morris sequence
* @param head
*/
public static void process(Node head) {
if (head == null) return;
Node cur = head; // The cur pointer, initially at the head node
Node mostRight = null; // the rightmost node of the left subtree
while (cur != null) {
mostRight = cur.left; // left tree
if (mostRight != null) { // left tree is not empty
// go right
while (mostRight.right != null && mostRight.right != cur) mostRight = mostRight.right;
// The right pointer of the rightmost node of the left subtree is empty, the first time
if (mostRight.right == null) {
// Point to the current node, then move cur to the left
mostRight.right = cur;
cur = cur.left;
continue;
} else {
// The right pointer of the rightmost node of the left subtree is not empty. For the second time, set the right pointer of mosrtRight to empty
mostRight.right = null;
}
}
// cur pointer to the right
cur = cur.right;
}
}
Morris preorder traversal
/**
* Morris preorder traversal
* @param head
*/
public static void processPre(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;
// The node with the left tree will be printed when it comes for the first time
System.out.println(cur.value);
cur = cur.left;
continue;
} else {
mostRight.right = null;
}
} else {
// There is no node in the left tree, directly print
System.out.println(cur.value);
}
cur = cur.right;
}
}
Morris inorder traversal
/**
* Morris Inorder traversal
* @param head
*/
public static void processIn(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;
}
}
// Regardless of whether there is a left tree or not, they will come here, and those who have a left tree will come here for the second time
System.out.println(cur.value);
cur = cur.right;
}
}
Morris post-order traversal
/**
* Morris Subsequent traversal
* @param head
*/
public static void processPost(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;
//Each time the node is returned for the second time, print the right edge of its left tree, in reverse order
printEdge(cur.left);
}
}
cur = cur.right;
}
//Finally, print the right boundary of the entire tree in reverse order
printEdge(head);
}
// Print the right edge of the tree in reverse order
private static void printEdge(Node head) {
// right boundary of tree, linked list reversed
Node tail = reverse(head);
Node cur = tail;
// Traverse the linked list to print
while (cur != null) {
System.out.println(cur.value);
cur = cur.right;
}
// return the linked list
reverse(tail);
}
// Reverse the right-bound list of a tree
private static Node reverse(Node head) {
Node pre = null;
Node cur = head;
Node right = null;
while (cur != null) {
right = cur.right;
cur.right = pre;
pre = cur;
cur = right;
}
return pre;
}
Morris traversal to determine whether a tree is a search binary tree
/**
* Morris Traverse to determine whether a tree is a search binary tree
* Created by huangjunyi on 2022/9/10.
*/
public class Morris02 {
private static class Node {
Node left;
Node right;
int value;
}
public static boolean isBST(Node head) {
if (head == null) return true;
Node cur = head;
Node mostRight = null;
//Take a variable preValue to record the value of the node traversed before
Integer preValue = 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;
}
}
// In the order of Morris in-order traversal, judge whether the value of the previous node is greater than the current node, if yes, return false, indicating that it is not a BST
// Here, I don’t care if the pointer of the tree is changed and messed up, all return false directly, otherwise it cannot return false directly, and return after traversing
if (preValue != null && cur.value <= preValue) return false;
preValue = cur.value;
cur = cur.right;
}
return true;
}
}
Morris traverses to find the height of the leaf node closest to the head node of a tree
/**
* Morris Traverse to find the height of the leaf node closest to the head node in a tree
* Created by huangjunyi on 2022/9/10.
*/
public class Morris03 {
private static class Node {
Node left;
Node right;
int value;
}
public static int getMinHigh(Node head) {
if (head == null) return 0;
Node cur = head;
Node mostRight = null;
int minHigh = Integer.MAX_VALUE;
int leftRightBoardsize = -1;
int curLevel = 0; // current node level
while (cur != null) {
mostRight = cur.left;
leftRightBoardsize = 1;
if (mostRight != null) {
//current node has left tree
while (mostRight.right != null && mostRight.right != cur) {
// Find the rightmost node of the left tree of the current node while recording the number of nodes at the right boundary of the left tree
mostRight = mostRight.right;
leftRightBoardsize++;
}
if (mostRight.right == null) {
// Entering here means coming to the current node for the first time
// Modify the right pointer of the rightmost node of the left tree to point to the current node, and move the cur pointer to the left node
mostRight.right = cur;
curLevel++;
cur = cur.left;
continue;
} else {
// Entering here means coming to the current node for the second time
// See if the left node of the rightmost node of the left subtree of the current node is empty, which means it is a leaf node
// It is found that the rightmost node of the left tree is a child node, clear it, and update minHigh
if (mostRight.left == null) {
minHigh = Math.min(minHigh, curLevel);
}
// curLevel is currently the height of the rightmost node of the left tree. Subtract the number of nodes at the right border of the left tree from leftRightBoardsize to obtain the height of the current node
curLevel -= leftRightBoardsize;
// Restores the right pointer of the rightmost node of the current node's left subtree
mostRight.right = null;
}
} else {
//The current node does not have a left tree, only the number of layers ++
curLevel++;
}
cur = cur.right;
}
return minHigh;
}
}
When to Traverse with Morris
Don’t use it in the written test, just use the most common and best recursion
During the interview, you can use Morris traversal to optimize
If the answers of the left and right subtrees are strictly required to integrate the answers of the current node, then only recursion can be used instead of Morris traversal
If it is not strictly dependent on the answers of the left and right subtrees, it can be optimized with Morris traversal