手撸二叉树之二叉树的层平均值

题目

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

解题思路

类似本题这种需要求解关于二叉树层次的，我们可以首先使用广度优先搜索。

从二叉树的根节点开始搜索，每一轮都遍历同一层的全部节点，计算该层的节点数以及该层节点之之和，然后再计算平均值。

说到广度优先搜索，就必须要用到队列这种数据结构来存储节点，确保每一轮遍历的时候，存储的都是同一层的节点；因为题目需要返回的是一个 List 数组，所以还需要定义一个 List 数组来存放平均值。

具体做法如下：

1. 初始化时，将根节点加入到队列中；
2. 遍历时，先将队列中的所有节点都取出，然后将取出的每个节点值求和；
3. 判断节点对的左右节点是否有值，有值就再次将他们的左右节点加入到队列中，保证每次遍历存储的都是同一层的节点；
4. 直到队列为空，遍历终止；

代码实现

/**
 * 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) {
        List<Double> results = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while (queue.size() != 0) {
            int size = queue.size();
            Double sum = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            Double average = sum / size;
            results.add(average);
        }   

        return results;
    }
}

最后

复杂度分析：

• 时间复杂度：O(n)，其中 n 是二叉树中的节点个数。
  广度优先搜索需要对每个节点访问一次，时间复杂度是 O(n)。

• 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。