二叉树的层平均值（Java）——算法刷题打卡

二叉树的层平均值

//节点的数据结构
  Definition for a binary tree node.
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
   TreeNode(int x) { val = x; }
}

对于此题而言，我们使用广度优先算法来遍历二叉树。

1、深度优先算法是根据二叉树的路径进行遍历
2、广度优先算法是根据二叉树的层级进行遍历

如何针对二叉树的层级进行遍历呢？

• 使用Queue队列，每遍历一层节点，则将该层节点出队，并将该层节点的子节点进队。

队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

• 因为队列的特殊性，当前层节点永远在队首，子节点永远在队尾。所以我们通过循环当前层的size次，就完成遍历当前层所有节点。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //结果集
        List<Double> resultList = new ArrayList<Double>();
        //队列，用来计算平均值
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //判断非空
        if(root == null) return resultList;
        //根节点入队
        queue.offer(root);
        //按层级循环，当队列为空时，则已经结束最后一层。则结束
        while(!queue.isEmpty()){
            //节点数
            double size = queue.size();
            //每层的节点和
            double sum = 0;
            //按每层节点数循环
            for(int i=0;i<size;i++){
                //出队
                root = queue.poll();
                //求和
                sum+=root.val;
                //判断是否存在左右节点，有则入队
                if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right);
            }
            //将每层的节点均值加入数组
            resultList.add(sum/size);
        }
        return resultList;
    }
}