AlgoViz Lab交互式算法学习Algorithms first
二叉树的层平均值 · 交互式算法学习
返回二叉树每层节点平均值。
#637 · 二叉树层次遍历
二叉树的层平均值
Average of Levels in Binary Tree
root = [3,9,20,null,null,15,7]树 / 图3 个关键状态
步骤 1记录当前队列长度 1。
n=1,sum=3推荐
队列按层累计
时间
O(n)空间 O(宽度)不保存整层值，只在出队时累加。
1function averageOfLevels(root) {2 const out = [],3 q = [root];4 while (q.length) {5 let sum = 0,6 n = q.length;7 for (let i = 0; i < n; i++) {8 const x = q.shift();9 sum += x.val;10 if (x.left) q.push(x.left);11 if (x.right) q.push(x.right);12 }13 out.push(sum / n);14 }15 return out;16}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val = val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {10 * this.val = val;11 * this.left = left;12 * this.right = right;13 * }14 * }15 */16class Solution {17 public List<Double> averageOfLevels(TreeNode root) {18 List<Double> ans = new ArrayList<>();19 Deque<TreeNode> q = new ArrayDeque<>();20 q.offer(root);21 while (!q.isEmpty()) {22 int n = q.size();23 long s = 0;24 for (int i = 0; i < n; ++i) {25 root = q.pollFirst();26 s += root.val;27 if (root.left != null) {28 q.offer(root.left);29 }30 if (root.right != null) {31 q.offer(root.right);32 }33 }34 ans.add(s * 1.0 / n);35 }36 return ans;37 }38}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
二叉树的层平均值 · 解法对比
返回二叉树每层节点平均值。
- 测试用例
root = [3,9,20,null,null,15,7]- 题目分类
- 二叉树层次遍历
- 解法对比
- 2
层序收集后求平均
BFS 把每层值放入数组，再求和除以数量。
- 时间
O(n)- 空间
O(n)
队列按层累计
不保存整层值，只在出队时累加。
- 时间
O(n)- 空间
O(宽度)