LeetCode 솔루션 분류
[9/2] 637. Average of Levels in Binary Tree
본문
Easy
4148273Add to ListShareGiven the
root
of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5
of the actual answer will be accepted.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [3.00000,14.50000,11.00000] 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].
Example 2:
Input: root = [3,9,20,15,7] Output: [3.00000,14.50000,11.00000]
Constraints:
- The number of nodes in the tree is in the range
[1, 104]
. -231 <= Node.val <= 231 - 1
Accepted
348,662
Submissions
489,053
태그
#Facebook
관련자료
-
링크
댓글 2
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 97 ms, faster than 23.20% of Python3 online submissions for Average of Levels in Binary Tree.
Memory Usage: 16.5 MB, less than 45.98% of Python3 online submissions for Average of Levels in Binary Tree.
Memory Usage: 16.5 MB, less than 45.98% of Python3 online submissions for Average of Levels in Binary Tree.
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
# bfs solution
queue = deque([root])
result = []
while queue:
this_level = []
for i in range(len(queue)):
node = queue.popleft()
this_level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(sum(this_level)/len(this_level))
return result
재민재민님의 댓글
- 익명
- 작성일
Runtime: 38 ms, faster than 15.57% of C++ online submissions for Average of Levels in Binary Tree.
Memory Usage: 22.5 MB, less than 29.85% of C++ online submissions for Average of Levels in Binary Tree.
Memory Usage: 22.5 MB, less than 29.85% of C++ online submissions for Average of Levels in Binary Tree.
/**
* 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) {
queue<TreeNode*> q;
vector<double> ans;
int current = 0;
int next = 0;
double sum = 0;
int count = 0;
TreeNode* node = nullptr;
if(root)
{
q.push(root);
current = 1;
while(!q.empty()) {
node = q.front();
q.pop();
if(node->left) {
q.push(node->left);
next++;
}
if(node->right) {
q.push(node->right);
next++;
}
sum += node->val;
count++;
if(count == current) {
ans.push_back(sum/count);
sum = 0;
count = 0;
current = next;
next = 0;
}
}
}
return ans;
}
};