637. 二叉树的层平均值

Posted on | In
Words count in article: 309 | Reading time ≈ 1

题目

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

示例 1:

1
2
3
4
输入：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:

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

提示：

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

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<Double> averageOfLevels(TreeNode root) {
        if (Objects.isNull(root)) {
            return Collections.emptyList();
        }
        List<Double> result = new ArrayList<>();
        result.add(root.val + 0.0);
        List<TreeNode> subNodes = new ArrayList<>();
        subNodes.add(root.left);
        subNodes.add(root.right);
        while (0 != subNodes.size()) {
            subNodes = subNodes.stream().filter(x -> !Objects.isNull(x)).collect(Collectors.toList());
            if (0 == subNodes.size()) {
                break;
            }
            long sum = 0;
            for (int i = 0;i < subNodes.size();i++) {
                sum += subNodes.get(i).val;
            }
            result.add((sum + 0.0) / subNodes.size());
            subNodes = getSubNodes(subNodes);
        }

        return result;
    }

    private List<TreeNode> getSubNodes(List<TreeNode> subNodes) {
        List<TreeNode> nodes = new ArrayList<>(subNodes.size() * 2);
        for (TreeNode node : subNodes) {
            nodes.add(node.right);
            nodes.add(node.left);
        }
        return nodes;
    }
0%