C# Beats 80% but with Unsolved Mystery


  • 0
    M

    This solution performs alright.

    I'm using a nested class to store the values I need to calculate the average per level. (This inner class stores the sum (numerator) and the number of values (denominator).)

    The weird part is... if I change the nested class to a nested struct instead, the algorithm fails.

    What's up with that?

    public class Solution {
        public class LevelSummary
        {
            public int Level;
            public double Sum;
            public int NoOfValues;
        }
        
        public IList<double> AverageOfLevels(TreeNode root) {
            
            // Process the input
            var levelSummaries = new List<LevelSummary>();
            AverageOfLevels_Recurse(root, 0, levelSummaries);
            
            // Prepare the output
            double[] output = new double[levelSummaries.Count];
            for (int level = 0 ; level < levelSummaries.Count; level++)
            {
                LevelSummary thisLevel = levelSummaries[level];
                output[thisLevel.Level] = thisLevel.Sum / thisLevel.NoOfValues;
            }
            return output;
        }
        
        private static void AverageOfLevels_Recurse(TreeNode node, int level, List<LevelSummary> levelSummaries)
        {
            // If necessary, create the summary object for this level.
            if (level > levelSummaries.Count - 1)
            {
                levelSummaries.Insert(level, new LevelSummary { Level = level });
            }
            
            // To store the averages, we will need the sum and the 
            var summary = levelSummaries[level];
            // Note: Delaying the average calculation reduces the chance of a rounding error.
            summary.Sum += node.val; // Increase the numerator for calculating averages.
            summary.NoOfValues += 1; // Increase the demoninator for calculating averages.
            
            // Process the left-branch.
            if (node.left != null)
            {
                AverageOfLevels_Recurse(node.left, level + 1, levelSummaries);
            }
            // Process the right-branch.
            if (node.right != null)
            {
                AverageOfLevels_Recurse(node.right, level + 1, levelSummaries);
            }
        }
    }
    

Log in to reply
 

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