【演算法從入門到放棄】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:n 3n / n 9 20n / n 15 7nOutput: [3, 14.5, 11]nExplanation:nThe 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].n

二叉樹或圖的遍歷有兩種方式：DFS( Depth First Search)和BFS(Breadth First Search)。

DFS中，我們挨個遍歷二叉樹的每一個分支

程序使用兩個數組保存中間結果：sum_list,保存每一層二叉樹的和，count_list，每一層二叉樹的節點數。遞歸調用average(t, i, sum_list, count_list)，每訪問一個節點，更新sum_list和count_list的值。

# Definition for a binary tree node.n# class TreeNode(object):n# def __init__(self, x):n# self.val = xn# self.left = Nonen# self.right = Nonenclass Solution(object):n def average(self,node,i,sum_list=None,count_list=None):n if node==None:n return n if i<len(sum_list):n sum_list[i]=sum_list[i]+node.valn count_list[i]+=1n else:n sum_list.append(node.val)n count_list.append(1)n self.average(node.left,i+1,sum_list,count_list)n self.average(node.right,i+1,sum_list,count_list)n def averageOfLevels(self,root):n """n :type root: TreeNoden :rtype: List[float]n """n sum_list=[]n count_list=[]n self.average(root,0,sum_list,count_list) n n for xx in range(len(sum_list)):n sum_list[xx]=float(sum_list[xx])/count_list[xx]n return sum_listn

推薦閱讀：