题目描述

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

样例

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

注意

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

算法

(深度优先遍历) $O(n)$

1. 从根结点开始进行深度优先遍历，遍历过程中按照当前的层数，将数值累计到数组中，同时自加该层结点个数的计数数组。
2. 本题也可采用宽度优先遍历的方式，方法大同小异。

时间复杂度

• 每个加点仅遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode *r, int level, vector<double> &ans, vector<int> &counter) {
        if (!r)
            return;
        if (ans.size() == level) {
            ans.push_back(0);
            counter.push_back(0);
        }
        ans[level] += r -> val;
        counter[level]++;
        dfs(r -> left, level + 1, ans, counter);
        dfs(r -> right, level + 1, ans, counter);
    }

    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        vector<int> counter;
        dfs(root, 0, ans, counter);
        for (int i = 0; i < ans.size(); i++)
            ans[i] /= counter[i];
        return ans;
    }
};