C# Simple O(n) Solution


  • 0
    K

    Calculate all the subtree sums. Map each sum to frequency in a dictionary. Return the most frequent sums.

    public class Solution {
        public int[] FindFrequentTreeSum(TreeNode root) {
            Dictionary<int, int> dict = new Dictionary<int, int>();
            Helper(root, dict);
            int max = 0;
            foreach(var key in dict.Keys){
                max = Math.Max(max, dict[key]);
            }
            List<int> output = new List<int>();
            foreach(var key in dict.Keys){
                if(dict[key] == max){
                    output.Add(key);
                }
            }
            return output.ToArray();
            
        }
        
        private int Helper(TreeNode node, Dictionary<int, int> dict) {
            if(node == null){
                return 0;
            }
            int sum = node.val;
            sum += Helper(node.left, dict);
            sum += Helper(node.right, dict);
            
            if(!dict.ContainsKey(sum)) {
                dict[sum] = 0;
            }
            dict[sum]++;
            return sum;
        }
    }
    

Log in to reply
 

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