preface

Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Their thinking

  • This problem belongs to the level traversal problem of binary tree
  • Let’s start by defining three arrays
  • The array queue is used to hold Pointers to all elements of the current layer
  • The temp array acts as a temporary array that holds the left and right Pointers to all the Pointers to the current element
  • The array test is used to hold the values of each layer of elements
  • When test has finished storing a layer of elements, it empties the queue and iterates through temp, placing the left and right children of each element in the queue for the next loop

The problem solving code

var levelOrder = function (root) {
    // The binary tree is traversed by a queue
    if (root === null) return [];
    let queue = [];
    const result = [];
    queue.push(root);
    while(queue.length ! = =0) {
        const temp = [];
        const test = [];
        for (let v of queue) {
            temp.push(v);
            test.push(v.val);
        }
        result.push(test);
        queue = [];
        for (let v of temp) {
            if(v.left ! = =null) {
                queue.push(v.left)
            }
            if(v.right ! = =null) {
                queue.push(v.right)
            }
        }

    }
    for (let i = 0; i < result.length; i++) {if (i % 2! = =0) {
            result[i] = result[i].reverse()
        }
    }
    return result;
};
Copy the code

conclusion

  • The problem at first glance is not difficult, we are also easy to think of certain ideas, but the difficult level of traversal
  • You can use one array to record the current layer and another array to record all the child nodes of the current layer. Then you can empty the current layer and continue traversing with the layers of all the child nodes.