01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第145題（順位題號是637）。給定一個非空二叉樹，以數(shù)組的形式返回每一層節(jié)點(diǎn)值之和的平均值。例如：

    3
   /   9  20
     /     15  7

輸出：[3,14.5,11]

說明：第一層上的節(jié)點(diǎn)的平均值為3，第二層上的節(jié)點(diǎn)的平均值為14.5，第三層上的節(jié)點(diǎn)的平均值為11.因此返回[3,14.5,11]。

注意：節(jié)點(diǎn)值的范圍在32位有符號整數(shù)的范圍內(nèi)。

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試。

02 第一種解法

使用廣度優(yōu)先算法（BFS）。使用隊列來實現(xiàn)，在遍歷節(jié)點(diǎn)的時候，使用了兩層循環(huán)，外層控制層數(shù)，內(nèi)層計算每一層的節(jié)點(diǎn)值之和，出了內(nèi)層循環(huán)后，在外層循環(huán)里計算平均值，將平均值添加進(jìn)數(shù)組中。其中有一點(diǎn)需要注意，計算節(jié)點(diǎn)值之和時，需要使用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<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<Double>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 控制層數(shù)，其大小就是當(dāng)前層數(shù)中包含的節(jié)點(diǎn)個數(shù)            
            int size = queue.size();
            int count = 0;
            // 使用long類型，避免溢出            
            long sum = 0;
            // 處理每一層的節(jié)點(diǎn)值
            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--;
            }
            // 計算平均值，添加進(jìn)數(shù)組
            list.add(sum*1.0d/count);
        }
        return list;
    }
}

03 第二種解法

使用深度優(yōu)先算法（DFS）。在使用深度優(yōu)先算法時，需要先將每一層的節(jié)點(diǎn)值之和單獨(dú)算出來，同時還要存儲每一層的節(jié)點(diǎn)個數(shù)，借助遞歸算法實現(xiàn)，在得到兩組數(shù)據(jù)后，再使用一次循環(huán)，計算每一層的平均值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        // 存放每一層的節(jié)點(diǎn)值總和
        List<Double> list = new ArrayList<Double>();
        if (root == null) {
            return list;
        }
        // 存放每層節(jié)點(diǎn)個數(shù)
        List<Integer> count = new ArrayList<Integer>();
        dfs(0, root, list, count);
        // 計算平均值
        for (int i=0; i<list.size(); i  ) {
            list.set(i, list.get(i)/count.get(i));
        }
        return list;
    }

    public void dfs(int deep, TreeNode root, List<Double> list, List<Integer> count) {
        if (root == null) {
            return ;
        }
        // 判斷是否還在當(dāng)前此層內(nèi)
        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);
        }
        // 遞歸調(diào)用剩下的節(jié)點(diǎn)
        dfs(deep 1, root.left, list, count);
        dfs(deep 1, root.right, list, count);
    }
}

04 小結(jié)

此題本質(zhì)上是對二叉樹的BFS、DFS算法的考察，在普通遍歷節(jié)點(diǎn)的基礎(chǔ)上，分層處理節(jié)點(diǎn)數(shù)據(jù)。

算法專題目前已日更超過四個月，算法題文章145 篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。