637. Average of Levels in Binary Tree
1. Description
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
2. Note
- The range of node’s value is in the range of 32-bit signed integer.
3. Solutions
Deep First Search
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
vector<double> averageOfLevels(const TreeNode* root) {
dfs(root, 0);
vector<double> averages(_max_level + 1);
for (int i = 0; i <= _max_level; ++i) {
averages[i] = _level_sum[i] / _level_node_count[i];
}
return averages;
}
private:
int _max_level;
unordered_map<int, int> _level_node_count;
unordered_map<int, double> _level_sum;
void dfs(const TreeNode* root, const int level) {
if (root != nullptr) {
_max_level = max(level, _max_level);
++_level_node_count[level];
_level_sum[level] += root->val;
dfs(root->left, level + 1);
dfs(root->right, level + 1);
}
}
};