leetcode 637. Average of Levels in Binary Tree 二叉树每层平均值+广度优先遍历BFS

￡神魔★判官ぃ 2022-06-03 05:38 136阅读 0赞

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.  
Example 1:  
Input:  
3  
/ \\  
9 20  
/ \\  
15 7  
Output: \[3, 14.5, 11\]  
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\].  
Note:  
The range of node’s value is in the range of 32-bit signed integer.

本题题意很简单，直接广度优先遍历BFS即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        vector<double> averageOfLevels(TreeNode* root) 
        {
            vector<double> res;
            if (root == NULL)
                return res;
            queue<TreeNode*> que;
            que.push(root);
            while (que.empty() == false)
            {
                double sum = 0;
                int size = que.size();
                for (int i = 0; i < size; i++)
                {
                    TreeNode* one = que.front();
                    que.pop();
                    sum += one->val;
                    if (one->left != NULL)
                        que.push(one->left);
                    if (one->right != NULL)
                        que.push(one->right);
                }
                res.push_back(sum / size);
            }
            return res;
        }
    };