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

preface

  • Hello everyone! Small du and you meet again, today to bring you is binary tree order traversal.
  • Qid for

  • After reading this article, you will find that the problem is surprisingly easy.
  • The code is small du in force buckle test, no problem!
  • This article is about binary treesPreemptive traversal of recursive and iterative code. If you want to learn the other two traversal methods, please slide to the bottom of the article
  • In the next article, Du is going to talk about the similarities and differences between their codes.
  • The purpose of this article
    • Master the preorder traversal of binary tree
    • Master the recursive and iterative code of the preorder traversal
    • The reader can complete the task independently144The title of the
  • Although small du love mumble, but can’t say again, should top dry goods!!

The body of the

  • Prep 1:

    • Binary treeThe former sequence traversalWhat is the order of theta?
    • Said the little du: parent – “left child -” right child
    • The example
    • The order of the figure above is,2,4,5,3,6 [1]
    • Can be understood like this: if this is 6 scenic spots, small du now want to travel, I first to 1 position, and then to 2 position… Every place I go I take a picture and then I go to the next place. Preorder traversal can be understood like this, you change the small du take a picture of the thing to print 1, print 2… That should make a little bit more sense. If you have any questions about this article, please point them out in the comments section. Thank you.

  • 1. The title is as follows

  • 2. Code implementation

    • thought: In the binary tree before the order traversal, the root node is the first to visit, similar to the first scenic spot of the small du tour, then find the left child, if the left child has, it has been looking for the left child of the left child… , until the left child of the current node is null, then find the right child of the current node…
    • The idea is not difficult, the binary tree preorder traversal should be the simplest of the three traversal, the most easy to understand.
    • Without further adoIteration code
    var preorderTraversal = function(root) { let res = []; Let stack = []; let stack = []; / / encountered in the process of circulation of node information while (root | | stack. The length) {/ / key1 while (root) {res. Push (root. Val); // Will encounter print, here is the store oh stack.push(root); // The node also needs to remember how to find its right child. root = root.left; } //key2 let node = stack.pop(); Root = node.right; } return res; };Copy the code

  • explain

    • Use the binary tree example shown above

    • Looking at the code, I’m going to go through the loop, go to key1, put 1 in the RES array, put 1 in the stack array, put 2 in the RES array, put 2 in the stack array, and then get to 4, and after doing that, Root = root.left, root is null, the loop exits and we need to start executing the code at key2. The last element of an array of the current stack are stored value for 4 node, to bring up this node (which means to remove and return the pop-up), and then find the node’s right child (because in key1 the cycle has turned the node’s left child find out, left child is null), readers can draw, after can deepen the impression.

    • The process of changing elements in the RES array:

      • [1]
      • [1, 2]
      • [1, 4-trichlorobenzene]
      • ,2,4,5 [1]
      • ,2,4,5,3 [1]
      • ,2,4,5,3,6 [1]

    • Recursive code, this little du thinks he has written very detailed, just look at it (hey hey hey)

    var preorderTraversal = function(root) { let res = []; // Const traversal = (root01)=>{// If the current node is null, if(root01 == null) return; Res.push (root01.val); // This path ends and needs to be retraced. Traversal (root01.left); Traversal of the left child (root01.right); } traversal(root); return res; // Return value};Copy the code

At the end

  • So far today, the three traversal method of binary tree is over, small du think speak very clearly, because small du themselves are clear.
  • The next article will look at the similarities and differences between their code.
  • Small du pen clumsy, have wrong place, welcome to point out, thank!!
  • Finally, I hope that after reading these articles, readers can write these three methods, when the interview in no panic!

If you can also click that like, pay attention to a wave, that is more nice!! Slip slip slip...

The attachment

  • Sequential traversal in a binary tree

    • The recursive version juejin. Cn/post / 702748…
    • Iterative version juejin. Cn/post / 702774…

  • Binary tree post order traversal juejin.cn/post/702911…