Leetcode637. BFS计算二叉树每层节点的平均值

￡神魔★判官ぃ 2021-09-15 03:38 277阅读 0赞

## 题目 ##

> Input:   
> 3   
> / \\   
> 9 20   
> / \\   
> 15 7
> 
> Output: \[3, 14.5, 11\]
> 
> Explanation:   
> The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return \[3, 14.5, 11\].

### 解题分析 ###

从题目的示例我们可以大概知道题目要求我们遍历二叉树的每层节点并计算其平均值。二叉树的搜索遍历无外乎这几种方法：先序遍历、中序遍历、后序遍历、BFS、DFS。结合题目，很显然BFS是比较适合题目的一种方法。那么问题来了，怎样使得二叉树每层的节点是从左至右遍历的，进而计算其节点个数和节点总和。

我们不妨用队列来思考这个问题。我们先往队列中push根节点，然后当队列不为空的时候，遍历整个队列。每遍历队列中的一个节点，就取出它的值并将其pop。此时顺带检查它的左右子节点是否为空，如果不为空，就将其子节点push进入队列中。这样，刚好遍历完一层节点，下一层的节点就全部存到队列中了。一层层循环下去直到最后一层，问题便顺利得到了解决。

方法一：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List < Double > averageOfLevels(TreeNode root) {
            List < Integer > count = new ArrayList < > ();
            List < Double > res = new ArrayList < > ();
            average(root, 0, res, count);
            for (int i = 0; i < res.size(); i++)
                res.set(i, res.get(i) / count.get(i));
            return res;
        }
        public void average(TreeNode t, int i, List < Double > sum, List < Integer > count) {
            if (t == null)
                return;
            if (i < sum.size()) {
                sum.set(i, sum.get(i) + t.val);
                count.set(i, count.get(i) + 1);
            } else {
                sum.add(1.0 * t.val);
                count.add(1);
            }
            average(t.left, i + 1, sum, count);
            average(t.right, i + 1, sum, count);
        }
    }

方法二

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List < Double > averageOfLevels(TreeNode root) {
            List < Double > res = new ArrayList < > ();
            Queue < TreeNode > queue = new LinkedList < > ();
            queue.add(root);
            while (!queue.isEmpty()) {
                long sum = 0, count = 0;
                Queue < TreeNode > temp = new LinkedList < > ();
                while (!queue.isEmpty()) {
                    TreeNode n = queue.remove();
                    sum += n.val;
                    count++;
                    if (n.left != null)
                        temp.add(n.left);
                    if (n.right != null)
                        temp.add(n.right);
                }
                queue = temp;
                res.add(sum * 1.0 / count);
            }
            return res;
        }
    }

不需要额外的queue：

public List<Double> averageOfLevels(TreeNode root) {
            List<Double> result = new ArrayList<>();
            if (root == null) {
                return result;
            }
            
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            double sum = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; ++i) {
                    TreeNode node = q.poll();
                    sum += node.val;
                    if (node.left != null) {
                        q.add(node.left);
                    }
                    
                    if (node.right != null) {
                        q.add(node.right);
                    }
                }
                
                result.add(sum / size);
                sum = 0;
            }
            
            return result;
        }