LeetCode演算法題-Average of Levels in Binary Tree（Java實現）
摘要：
這是悅樂書的第277
次更新，第293
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第145題（順位題號是637）。給定一個非空二叉樹，以陣列的形式返回每一層節點值之和的平均值。例如：
3
/...
這是悅樂書的第277 次更新，第293 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第145題（順位題號是637）。給定一個非空二叉樹，以陣列的形式返回每一層節點值之和的平均值。例如：
3 / \ 920 / \ 157
輸出：[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<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()) {
// 控制層數，其大小就是當前層數中包含的節點個數
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<Double> averageOfLevels(TreeNode root) {
// 存放每一層的節點值總和
List<Double> list = new ArrayList<Double>();
if (root == null) {
return list;
}
// 存放每層節點個數
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 ;
}
// 判斷是否還在當前此層內
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 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！