Simple Java solution - DFS


  • 0
    public class Solution {
        private class Pair {
            public long sum;
            public int count;
            public Pair(long sum, int count) {
                this.sum = sum;
                this.count = count;
            }
        }
        
        public List<Double> averageOfLevels(TreeNode root) {
            Map<Integer, Pair> pairs = new LinkedHashMap<>();
            calcPairs(root, 0, pairs);   
            List<Double> result = new ArrayList<>();
            for(Pair pair : pairs.values()) {
                result.add((double) pair.sum / (double) pair.count);
            }
            
            return result;
        }
        
        private void calcPairs(TreeNode node, int currLevel, Map<Integer, Pair> pairs) {
            if(node == null) {
                return;
            }
            
            Pair pair = pairs.get(currLevel);
            if(pair != null) {
                pair.sum += node.val;
                pair.count++;
                pairs.put(currLevel, pair);
            }
            else {
                pairs.put(currLevel, new Pair(node.val, 1));
            }
            
            calcPairs(node.left, currLevel + 1, pairs);
            calcPairs(node.right, currLevel + 1, pairs);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.