【力扣】637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

提示：

• 树中节点数量在 [1, 104] 范围内
• -231 <= Node.val <= 231 - 1

题解：

递归法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func averageOfLevels(root *TreeNode) []float64 {
	type data struct {
		sum, count int
	}
	var result []float64
	var depthData []data
	var order func(node *TreeNode, depth int)
	order = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if len(depthData) <= depth {
			depthData = append(depthData, data{})
		}
		depthData[depth].sum += node.Val
		depthData[depth].count++
		order(node.Left, depth+1)
		order(node.Right, depth+1)
	}
	order(root, 0)
	for _, d := range depthData {
		result = append(result, float64(d.sum)/float64(d.count))
	}
	return result
}