C++ BFS beat 100% at this time.


  • 0
    M

    The core idea is, whenever we reached the count of current level nodes, we calculate the average.

    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            if (root == nullptr)
            {
                return vector<double>();
            }
            
            queue<TreeNode*> q;
            q.push(root);
            
            int levelNodeNum = 1;
            int currentNodeNum = 0;
            double sum = 0;
            
            vector<double> res;
            
            while (!q.empty())
            {
                TreeNode* n = q.front();
                q.pop();
                
                if (n->left != nullptr)
                {
                    q.push(n->left);
                }
                
                if (n->right != nullptr)
                {
                    q.push(n->right);
                }
                
                sum += n->val;
                currentNodeNum++;
                
                if (currentNodeNum == levelNodeNum)
                {
                    res.push_back((double)sum / (double)currentNodeNum);
                    sum = 0;
                    currentNodeNum = 0;
                    levelNodeNum = q.size();
                }
            }
            
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.