Straightforward BFS question.
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res;
// sanity check
if (!root)
return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
double n = q.size(), temp = n;
double sum = 0;
while (temp--) {
TreeNode* top = q.front();
sum += top->val;
q.pop();
if (top->left) q.push(top->left);
if (top->right) q.push(top->right);
}
res.push_back(sum/n);
}
return res;
}
Time complexity: O(n)