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

preface

  • Yesterday did a binary tree in order to traverse the topic, using the recursive way to complete, today updated the second method, using the iterative method to complete the problem. During an interview, you’re more likely to be asked to write non-recursive code by hand, because recursion is just a few lines of code that you can read at a glance.

  • What is iteration?

    • In my understanding, iteration is the use of loop nesting, and then use auxiliary space, such as arrays and other data structures.

  • The harder the code is to write, the higher the quality is generally

  • The purpose of this article

    • 1. Middle order traversal process of binary tree
    • 2. Learn non-recursive code of sequential traversal, understand and master the implementation process of the code
    • 3. I hope this article has helped you learn how to write code

The body of the

  • Prep 1:
    • What does the left child, the right child, and the parent represent in a binary tree?

  • Prep 2:

    • What is the order of the middle order traversal?
    • Left child – parent – right child
    • The output order of the figure above is [4,2,5,1,3,6]
    • This should be easy to calculate, if not, welcome to leave a comment below, I will specifically explain it, also as a review for yourself!

  • La la la la, almost. Of course, you need to know the basics of loops and arrays

  • 1. The title is as follows

  • 2. Code implementation
    • The idea: First, we use a stack to hold the elements we encounter during the loop, and push the elements as we encounter them. So there’s another problem here, we can’t just go on the stack and not go off the stack, so when do we go off the stack?
    • We know that the middle-order traversal starts with the left child, so we should have the left child null, i.e., unstack when there is no left child (this is just my interpretation, different people interpret this differently), and that’s all we need to know.
    • The tree data structure, when encountered this type of problem, my understanding is to transform the problem into a node problem, the node can handle, then the other is roughly the same, and I think there are certain rules to follow the tree problem, this still needs to be discovered slowly.
    • Look directly at the code
var inorderTraversal = function(root) { let res = []; // Let stack = []; / / we are used to store encountered in the process of traverse of elements / / root = = null and stack length = = 0 exit (circulation) while (root | | stack. The length) {while (root) {/ / the current element is cycle stack.push(root); // Push the current element to the stack, not the value, but the entire current element root = root.left; } // This element has no left child, so we should print the element let target = stack.pop(); // Return this element and push res.push(target.val); // Push the value of this element into the stack to return root = target.right; } return res; // Return final result};Copy the code

  • explain

    • Outer loop of the judgment conditions (root | | stack. The length)
    • Conditions for loop exit
    • Root == null and stack.length == 0
    • Root == null means that you can’t find it if you continue in that direction, so you need to go back and try another direction
    • Stack.length == 0 means that all elements are already encountered and printed
    • Note: root is not null at first
    • Other important points are written in the code, if you have any questions about that part of the explanation, please feel free to ask.

At the end

  • I am clumsy, some places may be wrong, welcome to put forward.

  • I hope this article is helpful to you. If you feel that it is still useful, you are welcome to like it.