这是悦乐书的第277次更新，第293篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第145题（顺位题号是637）。给定一个非空二叉树，以数组的形式返回每一层节点值之和的平均值。例如：

3   / \  9  20     / \    15  7

输出：[3,14.5,11]

说明：第一层上的节点的平均值为3，第二层上的节点的平均值为14.5，第三层上的节点的平均值为11.因此返回[3,14.5,11]。

注意：节点值的范围在32位有符号整数的范围内。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

使用广度优先算法（BFS）。使用队列来实现，在遍历节点的时候，使用了两层循环，外层控制层数，内层计算每一层的节点值之和，出了内层循环后，在外层循环里计算平均值，将平均值添加进数组中。其中有一点需要注意，计算节点值之和时，需要使用long类型，避免溢出。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
    
      averageOfLevels(TreeNode root) {        List
     
       list = new ArrayList
      
       ();        if (root == null) {            return list;        }        Queue
       
         queue = new LinkedList
        
         ();        queue.offer(root);        while (!queue.isEmpty()) {            // 控制层数，其大小就是当前层数中包含的节点个数                        int size = queue.size();            int count = 0;            // 使用long类型，避免溢出                        long sum = 0;            // 处理每一层的节点值            while (size > 0) {                TreeNode temp = queue.poll();                count++;                if (temp != null) {                    sum += temp.val;                }                if (temp != null && temp.left != null) {                    queue.offer(temp.left);                }                if (temp != null && temp.right != null) {                    queue.offer(temp.right);                }                size--;            }            // 计算平均值，添加进数组            list.add(sum*1.0d/count);        }        return list;    }}
        
       
      
     
    

03 第二种解法

使用深度优先算法（DFS）。在使用深度优先算法时，需要先将每一层的节点值之和单独算出来，同时还要存储每一层的节点个数，借助递归算法实现，在得到两组数据后，再使用一次循环，计算每一层的平均值。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public List
    
      averageOfLevels(TreeNode root) {        // 存放每一层的节点值总和        List
     
       list = new ArrayList
      
       ();        if (root == null) {            return list;        }        // 存放每层节点个数        List
       
         count = new ArrayList
        
         ();        dfs(0, root, list, count);        // 计算平均值        for (int i=0; i
         
           list, List
          
            count) { if (root == null) { return ; } // 判断是否还在当前此层内 if (deep < list.size()) { list.set(deep, list.get(deep)+root.val); count.set(deep, count.get(deep)+1); } else { // 新的一层 list.add(1.0*root.val); count.add(1); } // 递归调用剩下的节点 dfs(deep+1, root.left, list, count); dfs(deep+1, root.right, list, count); }}
          
         
        
       
      
     
    

04 小结

此题本质上是对二叉树的BFS、DFS算法的考察，在普通遍历节点的基础上，分层处理节点数据。

算法专题目前已日更超过四个月，算法题文章145+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！