637. 二叉树的层平均值

Difficulty
easy
Tags
二叉树
二叉树层次遍历
URL
https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
Star
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
提示：
  • 节点值的范围在32位有符号整数范围内。

法1：宽度优先搜索

思路
同
🥎
102. 二叉树的层序遍历
🛷
107. 二叉树的层序遍历 II 类似都是层次遍历，只不过是把temp_list加到result的时候求得平均值再加入
题解
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue)
            temp_list = []
            while temp_len > 0:
                temp_node = queue.pop(0)
                temp_list.append(temp_node.val)
                temp_len -= 1

                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
            # 将该层平均值存到result中
            result.append(sum(temp_list)/len(temp_list))
        return result
优化
可以发现，其实没必要将 每一层的节点值保存下来 最后再求和求平均 ，完全可以 直接求和，最后再求平均 不过这样的话只能用 for循环了，因为while 每个循环会将 记录每层节点数的参数temp_len 减1
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue)
            temp_sum = 0
            for _ in range(temp_len):
                # 出队列 求和
                temp_node = queue.pop(0)
                temp_sum += temp_node.val
                # 子节点 入队
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
            # 将该层平均值存到result中
            result.append(temp_sum / temp_len)
        return result

法2 深度优先搜索

思路
参考
🥎
102. 二叉树的层序遍历
完整前序遍历一遍二叉树，遍历的过程将每一层的节点值之和 及每一层的节点个数 保存下来。然后再求得平均值
💡
求平均值时采用列表表达式求
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        res = []
        self.preOrder(node=root, result=res, depth=0)
				# 用列表表达式求均值
        return [i[0]/i[1] for i in res]

    def preOrder(self, node, result, depth):
        if node is None:
            return
        if len(result) <= depth:
            result.append([0, 0])
        result[depth][0] += node.val
        result[depth][1] += 1

        self.preOrder(node.left, result, depth+1)
        self.preOrder(node.right, result, depth+1)