本文主要是介绍【力扣】- 二叉树层平均值(层序遍历),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
题目链接
做法:
广度优先搜索进行层序遍历,问题点在于每次只求解当前这一层的节点的平均值。由于队列的特性为先进先出,加一个循环,循环当前队列的大小次并将这些元素出列:例如根节点循环一次即这一层的所有节点,循环一次,将它出列,将它的子节点入列。遍历每一层,求出平均值即可。
代码:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Double> averageOfLevels(TreeNode root) {Queue<TreeNode> q=new LinkedList<>();List<Double> averages=new ArrayList<>();q.add(root);while(!q.isEmpty()){int size=q.size();double sum=0,num=0;for(int i=0;i<size;i++){TreeNode node=q.poll();sum+=1.0*node.val;if(node.left!=null){q.add(node.left);}if(node.right!=null){q.add(node.right);}}num=sum/size;averages.add(num);}return averages;}
}
这篇关于【力扣】- 二叉树层平均值(层序遍历)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!