SlovinG
Search K

Appearance

637.二叉树的层平均值 ​

难度：容易

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

img

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

广度优先搜索法（BFS） ​

这道题和 102 题很类似，改动在于在每一层的遍历过程中，把该层的元素进行累计求和，计算完均值后，再将其放进 result 列表中。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

  1. 处理特例：若根节点为空，则返回空列表

  2. 根节点入队

  3. BFS 循环： 判断队列是否为空。如果不为空，说明还有节点需要遍历

    1. 初始化当前层的节点个数 currentLevelSize 为队列的大小
    2. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize
      1. 从队列中取出一个节点 current，将其元素值进行累计求和
      2. 如果当前节点有左子节点，将左子节点入队
      3. 如果当前节点有右子节点，将右子节点入队
    3. 对求和的结果进行平均值计算，并将其值加入结果列表 result
    4. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数

  4. 返回结果列表

代码展示 ​

java
public List<Double> averageOfLevels(TreeNode root){
        List<Double> result=new ArrayList<>();
        // 若根节点为空，则返回空列表
        if(root==null){
        return result;
        }
        Deque<TreeNode> queue=new LinkedList<>();
        // 根节点入队
        queue.add(root);
        // BFS 循环
        while(!queue.isEmpty()){
        int currentLayerSize=queue.size();
        Double layerSum=0.0;
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for(int i=0;i<currentLayerSize; i++){
        TreeNode current=queue.poll();
        layerSum+=current.val;
        if(current.left!=null){
        queue.add(current.left);
        }
        if(current.right!=null){
        queue.add(current.right);
        }
        }
        result.add(layerSum/currentLayerSize);
        }
        return result;
        }

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点 同时 在 queue 中，故使用 O(n) 大小的额外空间。

总结 ​

有时候要避免数据值溢出。