Java solution using DFS with full comments


  • 3
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            // list answer for sum all value in same level
            List<Double> answer = new ArrayList<Double>();
            
            // list counter for count number of node in same level
            List<Integer> counter = new ArrayList<Integer>();
            
            // using dfs to sum all value in same level and count number of node in same level
            dfs(0, root, answer, counter);
            
            // answer will be answer[level] / counter[level]
            for (int level = 0; level < answer.size(); level++) {
                answer.set(level, answer.get(level) / counter.get(level));
            }
            return answer;
        }
    
        public void dfs(int level, TreeNode node, List<Double> answer, List<Integer> counter) {
            if (node == null) {
                return;
            }
    
            if (answer.size() <= level) {
                answer.add(0.0);
                counter.add(0);
            }
    
            answer.set(level, answer.get(level) + node.val);
            counter.set(level, counter.get(level) + 1);
    
            // go left node and right node
            dfs(level + 1, node.left, answer, counter);
            dfs(level + 1, node.right, answer, counter);
        }
    }
    

Log in to reply
 

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