Easy

题目描述

给定一个二叉树的根节点 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, 10^4] 范围内。
  • -2^31 <= Node.val <= 2^31 - 1

解题思路

这道题要求计算二叉树每一层节点的平均值，是一道典型的层序遍历应用题。

思路分析

方法一：广度优先搜索（BFS）（推荐）

  • 使用队列进行层序遍历，每次处理一整层的节点
  • 对于每一层，记录节点的总数和总和，计算平均值
  • 将每层的平均值添加到结果数组中

方法二：深度优先搜索（DFS）

  • 使用递归遍历，同时记录当前节点的层级
  • 维护两个数组：一个存储每层的节点总和，一个存储每层的节点数量
  • 最后计算每层的平均值

BFS 方法更直观，因为我们是逐层处理的，符合题意。DFS 虽然也能解决问题，但需要额外的空间来存储每层的统计信息。

实现要点

  1. 使用队列存储每一层的节点
  2. 对于每一层，先确定该层的节点数量，然后逐个处理
  3. 计算平均值时注意使用浮点数除法
  4. 处理节点时将其非空子节点加入队列供下一层使用

代码实现

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        if (!root) return result;
        
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            long long sum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                sum += node->val;
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            result.push_back((double)sum / size);
        }
        
        return result;
    }
};

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            size = len(queue)
            level_sum = 0
            
            for _ in range(size):
                node = queue.pop(0)
                level_sum += node.val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level_sum / size)
        
        return result

public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        var result = new List<double>();
        if (root == null) return result;
        
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int size = queue.Count;
            long sum = 0;
            
            for (int i = 0; i < size; i++) {
                var node = queue.Dequeue();
                sum += node.val;
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            result.Add((double)sum / size);
        }
        
        return result;
    }
}

var averageOfLevels = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const size = queue.length;
        let sum = 0;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            sum += node.val;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(sum / size);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型BFS解法
时间复杂度O(n)
空间复杂度O(w)

其中 n 是树中节点的总数，w 是树的最大宽度（某一层的最大节点数）。在最坏情况下，完全二叉树的最大宽度约为 n/2，所以空间复杂度可以认为是 O(n)。

相关题目