[LeetCode] Average of Levels in Binary Tree

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
/**
* 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) {}
* };
*/
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;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/03/05/PS/LeetCode/average-of-levels-in-binary-tree/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.