建购物网站 教程千锋前端培训多少钱

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

提示：

• 树中节点数量在 [1, 104] 范围内
• -231 <= Node.val <= 231 - 1

代码：

/*** 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) {}* };*/
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> res;queue<TreeNode*> DS;int cnt;double sum;if(root == nullptr) return res;DS.push(root);while(!DS.empty()){sum = 0;cnt = DS.size();for(int i = 0; i < cnt; i++){TreeNode* p = DS.front();DS.pop();sum += p->val;if(p->right != nullptr){DS.push(p->right);}if(p->left != nullptr){DS.push(p->left);}}res.push_back(sum / cnt);}return res;}
};

解题思路：

（1）使用广度优先搜索。

（2）一次全部读出一层的节点，并进行计算平均值。