Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

144. Antecedent traversal of binary trees

Give you the root node of the binary tree, root, and return the preceding ** traversal of its node value.

 

Example 1:

Input: root = [1,null,2,3] output: [1, 3]Copy the code

Example 2:

Input: root = [] Output: []Copy the code

Example 3:

Input: root = [1] Output: [1]Copy the code

Example 4:

Input: root = [1,2] output: [2]Copy the code

Example 5:

Input: root = [1, NULL,2]Copy the code

 

Tip:

  • The number of nodes in the tree is in the range[0, 100] 内
  • -100 <= Node.val <= 100

 

Advanced: The recursive algorithm is simple, can you do it with an iterative algorithm?

Train of thought

  1. About the binary tree before the order traversal, if you do not know the little friends can have a look at my article, [Lufei]_ a thorough understanding of the binary tree before the order, order, order traversal;
  2. We’ve talked about recursion before, we’re not going to talk about it anymore, but I’m going to tell you how to do it with an iterative algorithm;
  3. There’s actually a very simple way to do this, we can use a stacknodeArrTo store. From top to bottom, if you have left node, we cache, later turn out their right child nodes, because the preorder traversal is to traverse all the nodes on the left, to the right node, so we took out a left on the bottom of the node of each round, whether it exists left child node, if there is continue to determine the next round, broken at the same timecur.leftOtherwise, the next round will fall into an infinite loop when it is taken out;
  4. If the bottom left node, there is no left child, then we need to print the right child, and the right child is printed from the bottom up in the first traversal, and that’s why we use the stack. And every time we take the last one, if we have a right child we put the right child back in for the next round to see if there are left and right children. Each time, the left child must be evaluated first, and then the right child, which means that the traversal is complete if the stack length is empty.

implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
    if(! root)return [];

    let nodeArr = [ root ];
    let result = [ root.val ];

    // Keep running when the stack is not empty
    while (nodeArr.length) {
        let cur = nodeArr[nodeArr.length - 1];
        // If there are left child nodes, save them and then save right child nodes one by one from bottom up
        // Remember to disconnect the cur.left link, otherwise the next round will come in a loop
        if (cur.left) {
            result.push(cur.left.val);
            nodeArr.push(cur.left);
            cur.left = null;
        } else {
            // There are no left child nodes
            let last = nodeArr.pop();
            // If there is a right child node, use it for the next round of judgment
            if (last.right) {
                result.push(last.right.val);
                nodeArr.push(last.right);
                cur.right = null; }}}return result;
};
Copy the code

conclusion

Encountered binary tree problems, the general use of recursive writing, but if you want to use iteration, the basic is to use stack or array storage. This is due to the nature of the stack: first in, last out, which makes it easier to print the desired value from the bottom up.

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.