1.問題描述

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.Example 1:Input:3/ \9 20/ \15 7Output: [3, 14.5, 11]Explanation: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].Note:1. The range of node's value is in the range of 32-bit signed integer.來自 <https://leetcode.com/problems/average-of-levels-in-binary-tree/description/>

2.題目分析

求二叉樹每一層的平均數，并存入到數組中，遍歷方法使用層序遍歷，關鍵是怎么判斷一層結束了，區別于層序遍歷的單隊列，這里使用了兩個隊列，一個存儲父節點層，另一個存儲子節點層，再父節點層遍歷完成后，計算均值并存儲，然后交換這兩個隊列，使得當前子節點層成為下一次計算的父節點層。結束的條件是兩個隊列都空了。需要注意的是，當父結點層存在，子結點層不存在，即最后一層時，并沒有計算最后一層均值，因此需要在循環結束時，計算最后一層均值并存儲。

3.C++代碼

//我的代碼：（beats 42%）vector<double> averageOfLevels(TreeNode* p){vector<double>r;queue<TreeNode*>q_root;queue<TreeNode*>q_child;q_root.push(p);int cnt = 0;double sum = 0;double aver = 0;while (!q_root.empty() || !q_child.empty()){if (!q_root.empty()){TreeNode *tmp = q_root.front();q_root.pop();if (tmp->left != NULL)q_child.push(tmp->left);if (tmp->right != NULL)q_child.push(tmp->right);cnt++;sum += tmp->val;}else{aver = sum / cnt;cnt = 0;sum = 0;q_root.swap(q_child);r.push_back(aver);}}aver = sum / cnt;r.push_back(aver);return r;}//改進版：（beats 74%）//只用一個隊列，每次大循環處理一行，而不是只處理一個結點//利用每一層的結點個數就是隊列的長度這一特點，減少一個隊列vector<double> averageOfLevels2(TreeNode* p){vector<double>r;queue<TreeNode*>q;q.push(p);int n = 0;double sum = 0;double aver = 0;while (!q.empty()){n = q.size();sum = 0;for (int i = 0; i < n; i++){TreeNode*tmp = q.front();q.pop();sum += tmp->val;if (tmp->left)q.push(tmp->left);if (tmp->right)q.push(tmp->right);}aver = sum / n;r.push_back(aver);}return r;}

總結

以上是生活随笔為你收集整理的637. Average of Levels in Binary Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。