Problem:
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
|
1 2 3 4 5 6 7 8 9 10 |
<b>Input:</b> 3 / \ 9 20 / \ 15 7 <b>Output:</b> [3, 14.5, 11] <b>Explanation:</b> The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11]. |
Time Complexity:
O(n)
Space Complexity:
O(h)
Solution 1:
BFS
|
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 |
// Author: Huahua class Solution { public: vector<double> averageOfLevels(TreeNode* root) { if(root == nullptr) return {}; vector<double> ans; vector<TreeNode*> curr, next; curr.push_back(root); // process every level one by one while(!curr.empty()) { long long sum = 0; for(const auto& node : curr) { sum += node->val; if (node->left) next.push_back(node->left); if (node->right) next.push_back(node->right); } ans.push_back(static_cast<double>(sum) / curr.size()); curr.swap(next); next.clear(); } return ans; } }; |
Solution 2:
DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: vector<double> averageOfLevels(TreeNode* root) { if(root == nullptr) return {}; vector<pair<long long, int>> sum_count; vector<double> ans; preorder(root, 0, sum_count); for(const auto& p : sum_count) ans.push_back(static_cast<double>(p.first) / p.second); return ans; } private: void preorder(TreeNode* root, int depth, vector<pair<long long, int>>& sum_count) { if(root == nullptr) return; if(depth>=sum_count.size()) sum_count.push_back({0,0}); sum_count[depth].first += root->val; ++sum_count[depth].second; preorder(root->left, depth+1, sum_count); preorder(root->right, depth+1, sum_count); } }; |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment