🥉637. 二叉树的层平均值🌱

🥉Easy

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

示例 1：
/

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

提示：

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

题解

此题就是二叉树的层次遍历变了形式而已，还是按照层次遍历的模板写就行

广度优先搜索

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        ans=[]
        if not root:
            return ans
        deque=[root]
        while len(deque):
            l=len(deque)
            sum=0
            for i in range(len(deque)):
                node = deque.pop(0)
                sum+=node.val
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
            ans.append(sum/l)
        return ans

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
    let ans=[]
    if (!root){
        return ans
    }
    let deque=[root]
    while(deque.length){
        let sum=0
        let len = deque.length
        for(let i=0;i<len;i++){
            let node = deque.shift()
            sum+=node.val
            if (node.left!== null){
                deque.push(node.left)
            }
            if(node.right!==null){
                deque.push(node.right)
            }
        }
        ans.push(sum/len)
    }
    return ans

};

复杂度分析

• 时间复杂度：，其中 n 是二叉树中的节点个数。广度优先搜索需要对每个节点访问一次，时间复杂度是 。需要对二叉树的每一层计算平均值，时间复杂度是，其中 h 是二叉树的高度，任何情况下都满足。因此总时间复杂度是 。

• 空间复杂度：，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。

深度优先搜索

除了广度优先搜索，自然就会有深度优先搜索。不过由于要计算层平均值，就需要两个数组。sums记录每一层节点和，counts记录节点个数。搜索的过程中需要记录当前节点所在的层，如果访问到的节点在第i层，则将counts[i]值加1，并将该节点的值加到sums[i]。

遍历结束之后，第i层平均值就是sums[i]/counts[i]。

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        counts = []
        totals = []
        def dfs(node, level):
            if not node:
                return
            if level < len(totals):
                totals[level] += node.val
                counts[level] += 1
            else:
                totals.append(node.val)
                counts.append(1)
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 0)
        return [total / count for total, count in zip(totals, counts)]

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var averageOfLevels = function(root) {
    let total=[]
    let count=[]
    function dfs(root,level){
        if (!root){
            return 
        }
        if (level<total.length){
            total[level]+=root.val
            count[level]+=1
        } else {
            total.push(root.val)
            count.push(1)
        }
        dfs(root.left,level+1)
        dfs(root.right,level+1)
    }
    dfs(root,0)
    let ans=[]
    for(let i=0;i<total.length;i++){
        ans.push(total[i]/count[i])
    }
    return ans
};

复杂度分析

• 时间复杂度：，其中 n 是二叉树中的节点个数。

深度优先搜索需要对每个节点访问一次，对于每个节点，维护两个数组的时间复杂度都是 ，因此深度优先搜索的时间复杂度是 。
遍历结束之后计算每层的平均值的时间复杂度是 ，其中 h 是二叉树的高度，任何情况下都满足 h≤n。
因此总时间复杂度是 。

• 空间复杂度：，其中 n 是二叉树中的节点个数。空间复杂度取决于两个数组的大小和递归调用的层数，两个数组的大小都等于二叉树的高度，递归调用的层数不会超过二叉树的高度，最坏情况下，二叉树的高度等于节点个数。