题目描述

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
注意：

节点值的范围在32位有符号整数范围内。

题目地址
中文版
英文版

代码实现

# 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]
		"""
		if not root:
			return []
		queue = [root]
		res = []
		while queue:
			tmp = []
			size = len(queue)
			for _ in xrange(size):
				node = queue.pop(0)
				tmp.append(node.val)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			res.append( sum(tmp)/float(len(tmp)) )
		return res
                                                                         

0 次阅读