力扣面试150题--二叉树的层平均值

Day 54

题目描述

思路

初次做法（笨）：使用两个队列，一个队列存放树的节点，一个队列存放对应节点的高度，使用x存放上一个节点，highb存放上一个节点的高度，sum存放当前层的节点值之和，num存放当前层的节点数。
当出现x节点与队列顶部的节点高度不同时，说明遍历到该层的最后一个元素，计算平均值放入结果集res，清空sum和num。
当出现x节点与队列顶部的节点高度相同时。说明是一层的节点，更新sum和num。
以上是判断时做的，以下是判断完做的
将x指向队列顶部元素，highb指向队列顶部元素的高度，弹出两个队列顶部元素，将x的左右子树放入队列，直到队列为空。

/**1. Definition for a binary tree node.2. public class TreeNode {3.     int val;4.     TreeNode left;5.     TreeNode right;6.     TreeNode() {}7.     TreeNode(int val) { this.val = val; }8.     TreeNode(int val, TreeNode left, TreeNode right) {9.         this.val = val;10.         this.left = left;11.         this.right = right;12.     }13. }*/
class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double>res=new ArrayList<Double>();if(root==null){return res;}Double sum=0.0;Double t=0.0;Queue<TreeNode>tree=new LinkedList<TreeNode>();Queue<Integer>high=new LinkedList<Integer>();tree.offer(root);high.offer(0);int highb=0;TreeNode x=root;int num=0;while(!tree.isEmpty()){if(highb==high.peek()){sum+=x.val;num++;}else{sum+=x.val;num++;res.add(sum/num);num=0;sum=0.0;}x=tree.poll();highb=high.poll();if(x.left!=null){tree.offer(x.left);high.offer(highb+1);}if(x.right!=null){tree.offer(x.right);high.offer(highb+1);}}sum+=x.val;num++;res.add(sum/num);return res;}
}

正确做法：不应该考虑高度的问题，原因在于我们在放入一层的元素后，该层元素的子树是在队列底部的，那么其实我们对于每层元素个数是清楚的，原因如下：

1. 我们清楚第0层只有根节点一个元素，将它的左右子树（非空的）放入队列后，再取出队列顶部元素，队列中剩下的都是第1层的元素，此时用一个参数记录即可。
2. 同理，我们第一层知道了元素个数，并且记录后，再将这一层的节点的子树放入队列，将这两个节点弹出，剩下的就是下一层的节点个数。
   因此有以下做法。

// 思路：使用BFS
// 使用BFS，将每一层的数字加起来，然后求平均值
// 总结：时间复杂度O（N）  空间复杂度O（N）
class Solution {public List<Double> averageOfLevels(TreeNode root) {//用于BFS的队列Queue<TreeNode> queue = new LinkedList<>();queue.add(root);//用于保存结果的数组List<Double> result = new ArrayList<>();double tempSum;//临时变量，记录每层节点相加的总和int tempCount;//临时变量，记录每层节点的个数TreeNode tempNode;//临时变量，方便BFS操作while (!queue.isEmpty()){//循环遍历每一层tempSum = 0.0;tempCount = queue.size();//记录当前层的元素个数for (int i = 0; i < tempCount; i++) {tempNode = queue.poll();if (tempNode.left != null) queue.offer(tempNode.left);if (tempNode.right != null) queue.offer(tempNode.right);tempSum += tempNode.val;//将每一层的节点值相加}result.add(tempSum / tempCount);//计算平均值，并加入结果集合中}//返回结果集合return result;}
}