leetcode 637. Average of Levels in Binary Tree

Myth丶恋晨 2022-06-09 09:25 231阅读 0赞

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:

  1. 3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

Output: [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].

注意每个节点上的值为32位有符号整数
Note:
The range of node’s value is in the range of 32-bit signed integer.

2.分析

广度优先遍历，对每一层的节点值求和，再取平均值。
注意：由于节点值32位整数，求和如果用int保存会溢出，而平均值是double类型。所以用double来保存求和

3.代码

  1. vector<double> averageOfLevels(TreeNode* root) {
  2.     queue<TreeNode*> nodes;
  3.     nodes.push(root);
  4.     vector<double> ans;
  5.     while (!nodes.empty()) {
  6.         int n = nodes.size();
  7.         int sum = 0;
  8.         for (int i = 0; i < n; i++) {
  9.             TreeNode* node = nodes.front();
  10.             sum += node->val;
  11.             nodes.pop();
  12.             if(node->left)
  13.                 nodes.push(node->left);
  14.             if(node->right)
  15.                 nodes.push(node->right);
  16.         }
  17.         ans.push_back((double)sum / n);
  18.     }
  19.     return ans;
  20. }

发表评论

表情：
评论列表 （有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读