Leetcode Study Day 39

Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].
Example 2:


Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
 

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Solution

To solve a breadth first search question, we use a queue. Queue’s feature is first in first out. So we can use it to store the nodes in the same level. We first push the root into the queue. Then we use a while loop to check if the queue is empty. If it is not empty, we get the size of the queue. The size of the queue is the number of nodes in the same level. We use a for loop to pop the nodes in the queue and add the value of the node to the sum. Then we check if the node has left child or right child. If it has, we push the child into the queue. After the for loop, we push the average of the sum and the size into the answer vector. Then we return the answer vector.

It is noticible that to convert int to double, we can firstly use (double) add an int, then the result will be double.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        queue<TreeNode*> treeQ;
        if(!root) return ans;
        treeQ.push(root);
        while(!treeQ.empty()){
            int size = treeQ.size();
            long sum = 0;
            for(int i = 0; i < size; i++){
                TreeNode* node = treeQ.front();
                treeQ.pop();
                sum += node->val;
                if(node->left) treeQ.push(node->left);
                if(node->right) treeQ.push(node->right);
            }
            ans.push_back((double)sum/size);
        }
        return ans;
    }
};