题目地址：https://leetcode.com/submissions/detail/136579829/open in new window
题目描述
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、 Therangeofnode'svalueisintherangeof32-bitsignedinteger.；
题目大意
求二叉树每层的所有节点的平均值
解题方法
方法一：DFS
这个题需要保存每层的节点的和以及每层的节点数。采用DFS的方式，把每个节点进行遍历，把这个节点加到对应层中去。每层使用两个数字，第一个数字保存所有节点的和，第二个数字保存有多少个节点。
注意一个小问题，节点为空的时候要return，否则下面node为None，出现错误。
# 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]
"""
info = [] the first element is sum of the level,the second element is nodes in this level
def dfs(node, depth=0):
if not node:
return
if len(info) <= depth:
info.append([0, 0])
info[depth][0] += node.val
info[depth][1] += 1
print(info)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root)
return [s / float(c) for s,c in info]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
二刷。直接使用数组保存每层所有节点的值，最后需要做个求平均数的处理。
# 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]
"""
res = []
self.getLevel(root, 0, res)
return [sum(line) / float(len(line)) for line in res]
def getLevel(self, root, level, res):
if not root:
return
if level >= len(res):
res.append([])
res[level].append(root.val)
self.getLevel(root.left, level + 1, res)
self.getLevel(root.right, level + 1, res)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
方法二：BFS
其实层次遍历使用BFS比使用DFS更加简单高效。因为每层遍历结束之后，已经知道了这一行的所有数字，所以可以直接求平均数，然后放入到结果中去，而不用最后才求平均数了。
# 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]
"""
que = collections.deque()
res = []
que.append(root)
while que:
size = len(que)
row = []
for _ in range(size):
node = que.popleft()
if not node:
continue
row.append(node.val)
que.append(node.left)
que.append(node.right)
if row:
res.append(sum(row) / float(len(row)))
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发