[LeetCode] 637. Average of Levels in Binary Tree

轉自LeetCode

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

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].

Note:

1. The range of node's value is in the range of 32-bit signed integer.

<Solution>

想法如下

• 用 level traversal 歷遍 tree，然後計算總和找出平均即可

• 要注意總和可能會超過 integer 的範圍

code 如下

Java

	/**
	* 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) {
	Queue<TreeNode> que = new LinkedList<>();
	List<Double> ans = new ArrayList<>();
	if(root != null) {
	que.offer(root);
	}
	double len;
	double sum;
	while(!que.isEmpty()) {
	len = que.size();
	sum = 0;
	for(int i = 0; i < len; i++) {
	root = que.poll();
	sum += root.val;
	if(root.right != null) {
	que.offer(root.right);
	}
	if(root.left != null) {
	que.offer(root.left);
	}
	}
	ans.add(sum / len);
	}
	return ans;
	}
	}

view raw averageOfLevels.java hosted with ❤ by GitHub