preface

Recursive traversal and iterative traversal of binary tree have been carried out before. In the first two traversal, the space complexity of binary tree traversal is O(n), because both recursive traversal and iterative traversal use stack space to help us maintain the call relationship, which is convenient for us to fall back when we reach the end point.

So, to think about it another way, can we not use the stack, but by recording the position of the node to fall back, help us to fall back directly to the target node? How do we maintain this back pointer? It can be found that the left and right Pointers of the leaf node of the binary tree are empty, and the position we need to back is triggered at the leaf node, so we can consider pointing the pointer of the leaf node to the target node, so that there is no need for extra stack space.

In fact, Morris traversal can reduce the spatial complexity of binary trees to O(1) by doing the same thing.

Morris traversal implementation principles

2. If cur has left children, find the right-most node on the cur tree. Call it Mostright

1) If the mostright pointer points to a cur, move it to the left (cur=cur.left) 2) If the mostright pointer points to a cur, move it to the right (cur=cur.right)Copy the code

The above is the rule of Morris traversal, where the node of Mostright is the pre-order node in the middle-order traversal. The essence of Morris traversal is that the node is traversed twice, one fast pointer and one slow pointer. When the slow pointer reaches a node, the fast pointer goes to the rightmost node of the left subtree of the current node, points the right pointer of the node to the position of the slow pointer, and then the slow pointer moves to the next step. In this way, when it falls back, it can quickly return to the target node through the pointer relationship established in the convenience process.

Morris pre-traversal Next, take a look at the implementation of Morris pre-traversal.

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } // TreeNode cur = root; TreeNode mostright = null; TreeNode mostright = null; while (cur ! = null) {// Fast pointer to left subtree mostright = cur.left; if (mostright ! While (mostright. Right! = null) {// While (mostright. Right! = null) { = null && mostright.right ! = cur) { mostright = mostright.right; If (mostright. Right == null) {// If (mostright. Right == null) {// If (mostright. mostright.right = cur; cur = cur.left; continue; } else {return ();} else {return ();} else {return (); Add (cur.val); // Add (cur.val); // Add (cur.val); } // If the left subtree is empty and the current node is recorded, go right // the cur pointer reaches the rightmost node of the left subtree of a node, return to that node cur = cur.right; } return res; }Copy the code

Morris sequence traversal

On the basis of the preceding traversal, the middle traversal needs to change the triggering time of the cur node

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } // TreeNode cur = root; TreeNode mostright = null; TreeNode mostright = null; while (cur ! = null) {// Fast pointer to left subtree mostright = cur.left; if (mostright ! While (mostright. Right! = null) {// While (mostright. Right! = null) { = null && mostright.right ! = cur) { mostright = mostright.right; } if (mostright. Right == null) {// If (mostright. Right == cur; cur = cur.left; continue; Add (cur.val); add(cur.val); add(cur.val); Mostright. Right = null; // The current node has a relationship with the right node (cur). Add (cur.val); // Add (cur.val); // Add (cur.val); } // If the left subtree is empty and the current node is recorded, go right // the cur pointer reaches the rightmost node of the left subtree of a node, return to that node cur = cur.right; } return res; }Copy the code