The topic of dry

Given a non-empty binary tree, return an array of the average values of the nodes at each level.

Example 1:

Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average value of layer 0 is 3, layer 1 is 14.5, and layer 2 is 11. So return [3, 14.5, 11].Copy the code

Tip:

  • The value of the node is in the range of 32 bit signed integers.

Source: LeetCode link: leetcode-cn.com/problems/av… Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Method: the BFS

We use the breadth-first search algorithm to traverse the binary tree, so as to calculate the result set of each layer and get the average value.

The idea is to use two queues, put the elements of the layer into the queue, and record the length of the current queue on each pass, as long as we keep the current queue as our layer’s data set at the start of each loop.

You can see the code implementation process

 var averageOfLevels = function (root) {
     let queue1 = [];
     let queue2 = [];
     if (root == null) {
         return null
     } else {
         queue1.push(root)
     }
     while(queue1.length ! = =0) {
        // Record the length of the current level
         let length = queue1.length;
         let sum = 0
          // Pop up the current level of data and calculate the total value
         for (let i = 0; i < length; i++) {
             let tempNode = queue1.shift();
             sum += tempNode.val
             if(tempNode.left ! = =null) {
                 queue1.push(tempNode.left)
             }
             if(tempNode.right ! = =null) {
                 queue1.push(tempNode.right)
             }
         }
         // Calculate the average value
         queue2.push(sum/length)
     }
     return queue2
 };
Copy the code