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: The range of node's value is in the range of 32-bit signed integer.
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
levels = []
def preorder(root, level):
if not root: return
if len(levels) == level:
levels.append([0, 0])
levels[level][0] += root.val
levels[level][1] += 1.0
preorder(root.left, level + 1)
preorder(root.right, level + 1)
preorder(root, 0)
return [item[0] / item[1] for item in levels]
Summary:
- dose 32-bit signed integer matter?
LeetCode: 637. Average of Levels in Binary Tree
近期评论