面试算法-65-二叉树的层平均值
题目
给定一个非空二叉树的根节点 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] 。
解
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> result = new ArrayList<>();LinkedList<TreeNode> queue1 = new LinkedList<>();LinkedList<TreeNode> queue2 = new LinkedList<>();queue1.offer(root);Double sum = 0D;int count = 0;while(!queue1.isEmpty()){TreeNode poll = queue1.poll();sum += poll.val;count++;if(poll.left != null){queue2.offer(poll.left);}if(poll.right != null){queue2.offer(poll.right);}if(queue1.isEmpty()){result.add(sum/count);queue1 = queue2;sum = 0D;count = 0;queue2 = new LinkedList<>();}}return result;}
}