Java

  • import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /**
    
     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:
     The range of node's value is in the range of 32-bit signed integer.
    
     */
    
    public class Average_of_Levels_in_Binary_Tree {
    
        /**
         * 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> result = new ArrayList<>();
    
                // bfs
                if (root == null) {
                    return result;
                }
    
                Queue<TreeNode> q = new LinkedList<>();
                q.offer(root);
                int currentLevelCount = 1;
                int nextLevelCount = 0;
    
                long currentLevelSum = 0;
                int count = 0;
    
                boolean isLevelLeftMost = false;
    
                while (!q.isEmpty()) {
                    TreeNode current = q.poll();
                    currentLevelCount--;
                    count++;
    
                    /*
    
                    overflow:
                    Input:
                            [2147483647,2147483647,2147483647]
                    Output:
                               [2147483647.0,-1.0]
    
    
    
                    short: 32767 or 0x7fff
                    int: 2147483647 or 0x7fffffff
                    size_t: 18446744073709551615 or 0xffffffffffffffff
                    streamsize: 9223372036854775807 or 0x7fffffffffffffff
                    float: 3.40282e+38 or 0x1.fffffep+127
                    double: 1.79769e+308 or 0x1.fffffffffffffp+1023
    
                    */
    
    
                    // @note:@memorize: overflow
                    // change sum from int to long
                    currentLevelSum += current.val;
    
                    if (current.left != null) {
                        q.offer(current.left);
                        nextLevelCount++;
                    }
                    if (current.right != null) {
                        q.offer(current.right);
                        nextLevelCount++;
                    }
    
                    if (currentLevelCount == 0) {
                        currentLevelCount = nextLevelCount;
                        nextLevelCount = 0;
    
                        // calculate avg
                        result.add(currentLevelSum * 1.0 / count);
    
                        count = 0;
                        currentLevelSum = 0;
                    }
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/average-of-levels-in-binary-tree/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            if (!root) return {};
            vector<double> ans;
            queue<TreeNode*> q;
            q.push(root);
            while (q.size()) {
                double cnt = q.size(), sum = 0;
                for (int i = 0; i < cnt; ++i) {
                    root = q.front();
                    q.pop();
                    sum += root->val;
                    if (root->left) q.push(root->left);
                    if (root->right) q.push(root->right);
                }
                ans.push_back(sum / cnt);
            }
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    from collections import deque
    
    
    class Solution(object):
      def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        ans = []
        queue = deque([root])
        while queue:
          s = 0
          n = len(queue)
          for _ in range(n):
            top = queue.popleft()
            s += top.val
            if top.left:
              queue.append(top.left)
            if top.right:
              queue.append(top.right)
          ans.append(float(s) / n)
        return ans
    
    

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) {
            List<Double> averages = new ArrayList<Double>();
            if (root == null)
                return averages;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                double sum = 0;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    sum += node.val;
                    TreeNode left = node.left, right = node.right;
                    if (left != null)
                        queue.offer(left);
                    if (right != null)
                        queue.offer(right);
                }
                double average = sum / size;
                averages.add(average);
            }
            return averages;
        }
    }
    
  • // OJ: https://leetcode.com/problems/average-of-levels-in-binary-tree/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        vector<double> averageOfLevels(TreeNode* root) {
            if (!root) return {};
            vector<double> ans;
            queue<TreeNode*> q;
            q.push(root);
            while (q.size()) {
                double cnt = q.size(), sum = 0;
                for (int i = 0; i < cnt; ++i) {
                    root = q.front();
                    q.pop();
                    sum += root->val;
                    if (root->left) q.push(root->left);
                    if (root->right) q.push(root->right);
                }
                ans.push_back(sum / cnt);
            }
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    from collections import deque
    
    
    class Solution(object):
      def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        ans = []
        queue = deque([root])
        while queue:
          s = 0
          n = len(queue)
          for _ in range(n):
            top = queue.popleft()
            s += top.val
            if top.left:
              queue.append(top.left)
            if top.right:
              queue.append(top.right)
          ans.append(float(s) / n)
        return ans
    
    

All Problems

All Solutions