Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

Topic describes

Give you a binary tree, and shine a light from the left. Return all the nodes that can be hit by the light.

The above binary tree, seen from the left, has nodes [1,2,4,7]

Subject analysis

We can see that this is actually the first node of each layer, so we can use the binary tree to solve the sequence traversal.

In general, the sequential traversal of binary trees can use a queue to temporarily store nodes of each layer, for example:

1. Firstly, the node of the first layer is queued, and the length of the queue is 1. Then the current layer needs to traverse once, and a node is queued, and the children of the node are queued

2. At this time, the queue length is 2, so the current layer needs to traverse twice. Second time: out of team 3,3 children in the team

3. The initial number of layers is 0. After each layer is traversed, the number of layers +1 until the queue is empty

Code 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 levelOrder = function (root) {
    if(! root)return []
    // First the root node joins the queue
    const queue = []
    queue.push(root)
    const res = []
    // The root node is at layer 0
    let level = 0
    while (queue.length) {
        // Get the number of nodes in the current layer
        const curLevelSize = queue.length
        // Initializes the current layer array to hold the nodes of the current layer
        res[level] = []
        // There are several nodes in the current layer, so we need to traverse several times
        for (let i = 0; i < curLevelSize; i++) {
            // walk through one node at a time
            const node = queue.shift()
            // Add this node to the array of the current layer
            res[level].push(node.val)
            // Let the children join the team
            if (node.left) queue.push(node.left)
            if (node.right) queue.push(node.right)
        }
        // When the current layer is traversed, the number of layers is +1
        level++
    }
    return res
};
Copy the code

Perform results and complexity analysis

Time complexity: O(n), each node is traversed once

Space complexity: O(n), the number of elements in the queue does not exceed N