02、二叉树的层平均值

这个题也同样如此，学会了二叉树的层序遍历，这个题目直接能够解决

题目链接：637. 二叉树的层平均值 - 力扣（LeetCode）

一、题目描述

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

示例 1：

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

        3
       / \
      9  20
        /  \
       15   7

解释：

• 第 1 层：平均值 = 3 / 1 = 3.00000
• 第 2 层：平均值 = (9 + 20) / 2 = 14.50000
• 第 3 层：平均值 = (15 + 7) / 2 = 11.00000

示例 2：

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

        3
       / \
      9  20
     / \
   15   7

数据范围：

• 树中节点数量在 [1, 10^4] 范围内
• -2^31 <= Node.val <= 2^31 - 1

题目分析

这道题是层序遍历的经典应用，需要计算每一层节点的平均值。那我们无非就是记录这一层的总和，然后求一下平均值，那我们来看一下，该题目的核心解题思路

核心思路

1. 按层遍历二叉树
2. 计算每一层所有节点值的和
3. 除以该层的节点数量得到平均值

关键点

• 需要区分每一层的节点
• 需要计算每层的节点总和和节点数量
• 注意数据类型：使用 double 避免整数除法
• 注意溢出：节点值可能很大，求和时可能溢出

层序遍历

算法思路

1. 使用队列进行层序遍历
2. 遍历每一层时，累加所有节点值
3. 用总和除以节点数得到平均值

图解过程

以 root = [3,9,20,null,null,15,7] 为例：

        3
       / \
      9  20
        /  \
       15   7

第 1 层：[3]           → 和 = 3,  节点数 = 1,  平均值 = 3.0
第 2 层：[9, 20]       → 和 = 29, 节点数 = 2,  平均值 = 14.5
第 3 层：[15, 7]       → 和 = 22, 节点数 = 2,  平均值 = 11.0

结果：[3.0, 14.5, 11.0]

C++ 实现

#include <vector>
#include <queue>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;

        // 题目保证树非空，但为了代码健壮性还是检查一下
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            double sum = 0;  // 使用 double 避免整数除法

            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; 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(sum / levelSize);
        }

        return result;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。

空间复杂度：O(w)，其中 w 是二叉树的最大宽度。队列中最多存储一层的节点。