Binary tree brush inscription (three – after traversal)

This is the third day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

preface

• Today, I did the post order traversal topic about binary tree. My plan is to master the first, middle and last three traversal calculation methods of binary tree, and then do other topics about binary tree.

• Today there is no separation between recursive and iterative code! All together.

• My recent feeling: if you don’t understand the problem, go directly to the solution. If you don’t understand the solution, go directly to the code, then take an example to go through the program, and finally turn over the head to see the solution. I think it’s almost the same if you don’t understand it.

• Important: remember to type several times after understanding, it is best to form a conditioned reflex, as soon as you see this problem you know what the code is.

• Goal: not all will, we can not do, just we have done you can make enough.

• The purpose of this article

  • Master the backward traversal process of binary tree.
  • Master the recursive and iterative code of post-sequence traversal.
  • Hopefully, dear readers, by the end of this article, they can master these two algorithms.

The body of the

• Prep 1:

  • By default, the reader understands the basic concepts of binary trees.

• Prep 2:

  • What is the order of the backward traversal?
  • Left child – right child – parent
  • The example

  

  • The order of the figure above is [4,5,2,6,3,1]
  • If you have any questions, please leave them in the comments below and let’s learn together!

• 1. The title is as follows

• 2. Code implementation

  • Idea: In a back-order traversal, each parent node is the last to be accessed, while the root node is accessed only after all elements have been accessed.
  • Iteration code

  var postorderTraversal = function(root) { let res = []; // Let stack = []; / / encountered in the process of traverse of element nodes while (root | | stack. The length) {while (root) {res. Unshift (root. Val); // Insert stack.push(root); // Insert stack.push(root); root = root.right; } let node = stack.pop(); root = node.left; } return res; };Copy the code

• explain

  • This code looks for the parent, and then always looks for the child to the right of the parent. Can you see that?

  • Each time a node is encountered, the value of val is inserted into the returned array using the header method. This process, this is the heart of the algorithm, and if you understand it, this code will make sense. If root is null, return will not enter the loop. Instead, insert the val header of the root node into the RES array, insert the whole root node into the stack array, find its right child, if any, and continue the loop, where we know that every time we loop, we always insert the val of one node into the first position of the RES array.

  • Summary: The val value of the root element is placed at the end of the res array. We find the parent of the root element in the order of “right child” and “left child”. The output order is “left child” and “right child”. (Because we’re using a head plug)

  • Here we go again from the diagram above. Please bear with me, believe me, after reading do not understand you beat me.

  • The process of changing elements in the RES array

    • [1]
    • (3, 1)
    • ,3,1 [6]
    • ,6,3,1 [2]
    • ,2,6,3,1 [5]
    • ,5,2,6,3,1 [4]
    • Isn’t that what we want in the backward traversal order?
    • That’s it. Any questions please leave a comment below.

  • Recursive code

  var postorderTraversal = function(root) { let res = []; // Const traversal = (root01)=>{if(root01 == null) return; Traversal (root01.left); // Switch traversal(root01.left); Traversal (root01.right); // Traversal (root01.right); // Traverse the right subtree res.push(root01.val); // Left and right subtree traversal is left in the middle! } traversal(root); return res; };Copy the code

  • Recursion has a problem, small du suggest you do the problem when you can draw below, see the code side draw, soon you will understand.

At the end

• If you read this article carefully, I’m sure you will.
• Next time, I’ll write a piece on the iterative and recursive code of the preceding iteration and see if I can find commonalities between them.
• I am clumsy, some places to write wrong, welcome to point out, thank you!!
• In the end, I wish you all a good read this article, we will see you next time.