LeetCode Average of Levels in Binary Tree

LeetCode Average of Levels in Binary Tree

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   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].

Note:

  1. The range of node's value is in the range of 32-bit signed integer.

求二叉树每一层的平均数。简单题,BFS层次遍历。代码如下:

class Solution {
public:
	vector<double> averageOfLevels(TreeNode* root) {
		if (root == NULL)return{};
		vector<double> ans;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			double sum = 0;
			size_t n = q.size();
			for (size_t i = 0; i < n; ++i) {
				TreeNode* f = q.front();
				q.pop();
				sum += f->val;
				if (f->left != NULL)q.push(f->left);
				if (f->right != NULL)q.push(f->right);
			}
			ans.push_back(sum / n);
		}
		return ans;
	}
};

本代码提交AC,用时15MS。

Leave a Reply

Your email address will not be published. Required fields are marked *