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

107. Sequence traversal of binary trees II

Given a binary tree, return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

For example, given a binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Return its bottom-up sequence traversal as:

[[15,7], [9,20], [3]Copy the code

Train of thought

  1. First, we can use a stack that keeps track of the valid nodes at each level, so the stack looks like this[Level 1 [], level 2 []...];
  2. When all the records are finished, they are removed from the stack one by one, and the values are recorded in another stack of results, and then the results are printed.
  3. Or you can simply take the result record and move it from one stack to another, flipping the elements in that stack over;
  4. The advantage of the JS array is that we can insert elements at the front of the array, which means that we do not need to flip the operation directly, each round of the insert to the front.

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 levelOrderBottom = function(root) {
    if(! root)return [];

    // Output from left to right, with queue first in first out
    let queue = [ root ];
    let result = [];

    // There is the next round to execute
    while (queue.length) {
        // Record the current value
        let temp = [];
        queue = queue.reduce((total, cur) = > {
            // Record the current value
            temp.push(cur.val);

            // Record the valid value of a round
            cur.left && total.push(cur.left);
            cur.right && total.push(cur.right);
            returntotal; } []);// This step is key, because the js array naturally comes with an insert method from the head, so it saves a lot of work
        // If there are only stacks and queues, then we need to store the first stack and remove the queue one by one to reverse the order
        result.unshift(temp);
    }

    return result;
};
Copy the code

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.