This is the 28th day of my participation in the August Text Challenge.More challenges in August

Middle order traversal of binary trees

144. Antecedent traversal of binary trees

145. Back-order traversal of binary trees

Today in the review of tree related knowledge when I thought of the above problem, if you use recursion to solve it is actually very simple.

However, if you use iteration instead of recursion, you won’t be able to figure it out for a while, so let’s summarize the process of converting a tree recursion to iteration.

We apply recursion to the next boundary condition: recursion: calls itself until the boundary condition is encountered.

In recursion, the underlying flow is:

  • Push the current data onto the method stack
  • The incoming data is used for the next step of recursion

Therefore, in the process of recursion to iteration, the most important thing is to determine the current position.

Take the traversal above for example:

  • Pre-traversal is the easiest, so let’s start here.
Public static void preOrderTraversalR(List<Integer> List,TreeNode cur){list.add(cur.val); inorderTraversalR(list,cur.left); inorderTraversalR(list,cur.right); } public static List<Integer> preOrderTraversal(TreeNode root) {Deque<TreeNode> STK = new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); While (root! =null || ! stk.isEmpty()){ if(null == root) root = stk.pop(); res.add(root.val); if(null! =root.right)stk.push(root.right); root = root.left; } return res; }Copy the code

After comparison, it can be found that:

  • When iterating, our operations have some fixed relationships compared to recursion:

    • Recursively first, in the iteration is the next execution object
    • The overall flow of our iteration is until we find the next object to add to the result set

So, based on this discovery, let’s try to write the middle order ergodic:

public static void inorderTraversalR(List<Integer> list,TreeNode cur){ inorderTraversalR(list,cur.left); list.add(cur.val); inorderTraversalR(list,cur.right); } public static List<Integer> inorderTraversal(TreeNode root) { Deque<TreeNode> stk = new LinkedList<>(); List<Integer> res = new ArrayList<>(); while(root! =null || ! Stk.isempty ()){// inorderTraversalR(list,cur.left); while(root! =null){ stk.push(root); root = root.left; } // list. Add (cur.val); root = stk.pop(); res.add(root.val); // inorderTraversalR(list,cur.right); root = root.right; } return res; }Copy the code

The sequence traversal flow is as follows:

  • Left to far left
  • The results of
  • Follow the same process to the right

In fact, there is a small problem that will be encountered in the following sequence traversal, which is:

  • Do we need a node to record a location?

No, we don’t, because we’re in left-center-right order, which means we don’t have to go through the middle nodes again.

Similarly, the following order traversal can be obtained:

public static void postOrderTraversalR(List<Integer> list,TreeNode cur){ inorderTraversalR(list,cur.left); inorderTraversalR(list,cur.right); list.add(cur.val); } public static List<Integer> postOrderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Deque<TreeNode> stack = new LinkedList<>(); TreeNode prev = null; while(null! =root || ! stack.isEmpty()){ //inorderTraversalR(list,cur.left); while(null! =root){ stack.push(root); root = root.left; } //list.add(cur.val); root = stack.pop(); // if(root.right==null || root.right==prev){ res.add(root.val); Prev = root; prev = root; prev = root; root = null; }else{ //inorderTraversalR(list,cur.right); stack.push(root); root = root.right; } } return res; }Copy the code

The back-order traversal is a bit more cumbersome because we traverse in left-right order, which means we need to keep track of the right nodes we visit, otherwise we’ll get stuck in an endless loop.

It doesn’t matter if you can’t understand it here, you can write it down first and then slowly digest it.

\