637. Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Note:
The range of node’s value is in the range of 32-bit signed integer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
template <typename T, typename U> std::pair<T, U> operator+(const std::pair<T,U>& l, const std::pair<T,U>& r) { return {l.first + r.first, l.second + r.second}; } class Solution { private: map<int, pair<long, int>> levelSum;
void recursiveSumTree(int level, TreeNode* node) { if(!levelSum.count(level)) { levelSum[level] = {0, 0}; } pair<long, int> cur = {node->val, 1}; levelSum[level] = cur + levelSum[level];
if(node->left != nullptr) { recursiveSumTree(level + 1, node->left); }
if(node->right != nullptr) { recursiveSumTree(level + 1, node->right); }
return; } public: vector<double> averageOfLevels(TreeNode* root) { recursiveSumTree(0, root);
vector<double> res; for(auto entity : levelSum) { res.push_back(1.0 * entity.second.first / entity.second.second); }
return res; } };
|