Verbose Java solution, postOrder traverse, HashMap (18ms)


  • 28

    For sake of saving time during contest, can't write so concise solution :)
    Idea is post-order traverse the tree and get sum of every sub-tree, put sum to count mapping to a HashMap. Then generate result based on the HashMap.

    public class Solution {
        Map<Integer, Integer> sumToCount;
        int maxCount;
        
        public int[] findFrequentTreeSum(TreeNode root) {
            maxCount = 0;
            sumToCount = new HashMap<Integer, Integer>();
            
            postOrder(root);
            
            List<Integer> res = new ArrayList<>();
            for (int key : sumToCount.keySet()) {
                if (sumToCount.get(key) == maxCount) {
                    res.add(key);
                }
            }
            
            int[] result = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                result[i] = res.get(i);
            }
            return result;
        }
        
        private int postOrder(TreeNode root) {
            if (root == null) return 0;
            
            int left = postOrder(root.left);
            int right = postOrder(root.right);
            
            int sum = left + right + root.val;
            int count = sumToCount.getOrDefault(sum, 0) + 1;
            sumToCount.put(sum, count);
            
            maxCount = Math.max(maxCount, count);
            
            return sum;
        }
    }
    

  • 1

    Same general concept except you can actually form the result array as you go. Think about the result array will contain the sums with highest frequency. Every time you update your sum to frequency map you can check if this sum is now the highest frequency by comparing it to the frequency of the first sum in your list. If your list is empty add this sum. When you have a tie add your sum to the list, when you have a new highest clear the list then add it.

        public int[] FindFrequentTreeSum(TreeNode root) 
        {
            IList<int> items = new List<int>();
            int total = Find(root, new Dictionary<int,int>(), items);
            return items.ToArray();
        }
        
        public int Find(TreeNode node, Dictionary<int,int> map, IList<int> items)
        {
            if (node == null) return 0;
            int sum = node.val + Find(node.left, map, items) + Find(node.right, map, items);
            if (!map.ContainsKey(sum)) map[sum] = 0;
            
            int currCnt = items.Count > 0 ? map[items[0]] : 0;
            map[sum]++;
            
            if (map[sum] == currCnt) 
            {
                items.Add(sum);
            }
            else if (map[sum] > currCnt)
            {
                items.Clear();
                items.Add(sum);
            }
            
            return sum;
        }
    

  • 2
    M

    Exact same logic as yours.Instead of creating a new arraylist,I maintained a variable which keeps track of the total number of elements with maximum count.

        int max=0,num=0;
        public int[] findFrequentTreeSum(TreeNode root) {
            int temp = inorder(root);
            
            int[] freqsum = new int[num];
            int i=0;
            for(int x : count.keySet())
            {
                if(count.get(x)==max)
                {
                    freqsum[i]=x;
                    i++;
                }
            }
            return freqsum;
        }
        
        int inorder(TreeNode root)
        {
            if(root==null)
                return 0;
                
            int left = inorder(root.left);
            int right = inorder(root.right);
            int sum = left+right+root.val;
            
            int temp = count.getOrDefault(sum,0)+1;
            if(max==temp)
                num++;
            else if(temp>max)
            {
                max=temp;
                num=1;
            }
            count.put(sum,temp);
            
            return sum;
            
        }

  • 2
    1. get sum for each subtrees, adding sum and count to a map
    2. find the max count
    3. if the count equals max count, add that sum to result.
    public int[] findFrequentTreeSum(TreeNode root) {
      Map<Integer,Integer> map = new HashMap();
      helper(map, root);  
      int max = 0;
      for (int key : map.keySet()) {
        max = Math.max(max, map.get(key));
      } 
      
      List<Integer> res = new ArrayList();
      for(int key: map.keySet()){
        if(map.get(key) == max) res.add(key);
      }     
      
      int[] result = new int[res.size()];
      for(int i = 0; i < res.size(); i++){
        result[i] = res.get(i);  
      }
      return result; 
    }
    
    int helper(Map<Integer,Integer> map, TreeNode root){
      if(root == null) return 0;
      int left = helper(map, root.left);
      int right = helper(map, root.right);
      int sum = left + right + root.val;
      int count = map.getOrDefault(sum, 0);
      map.put(sum, count + 1);
      return sum;
    }

  • 4

    Similar solution without browsing the whole hashmap again to find frequent sums. (Why I do this? Because I was asked to do so during an interview...)

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int fre = 0;
        List<Integer> res = new ArrayList<Integer>();
        public int[] findFrequentTreeSum(TreeNode root) {
            if(root == null) return new int[0];
            
            helper(root);
            
            int[] ret = new int[res.size()];
            for(int i = 0; i < res.size(); i ++){
                ret[i] = res.get(i);
            }
            return ret;
        }
        public void helper(TreeNode root){
            if(root == null) return ;
            int sum = computeSum(root);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            if(map.get(sum) == fre){
                res.add(sum);
            }else if(map.get(sum) > fre){
                res.clear();
                res.add(sum);
            }
            fre = Math.max(fre, map.get(sum));
            
            helper(root.left);
            helper(root.right);
        }
        public int computeSum(TreeNode root){
            int s = root.val;
            if(root.left != null) s += computeSum(root.left);
            if(root.right != null) s += computeSum(root.right);
            return s;
        }
    

  • 0

    Similar idea... 16 ms.

    '''
    public class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
    if (root == null) {
    return new int[0];
    }

    	Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
    	findSum(root, freq);
    	int max = Integer.MIN_VALUE;
    	List<Integer> list = new ArrayList<Integer>();
    	Iterator<Map.Entry<Integer, Integer>> itr = freq.entrySet().iterator();
    	while (itr.hasNext()) {
    		Map.Entry<Integer, Integer> entr = itr.next();
    		if (entr.getValue() == max) {
    			list.add(entr.getKey());
    		} else if (entr.getValue() > max) {
    			max = entr.getValue();
    			list.clear();
    			list.add(entr.getKey());
    		}
    	}
    	
    	int[] result = new int[list.size()];
    	int i = 0;
    	while (i < list.size()) {
    		result[i] = list.get(i++);
    	}
    
    	return result;
    }
    
    int findSum(TreeNode node, Map<Integer, Integer> freq) {
    	if (node == null) {
    		return 0;
    	}
    
    	int sum = findSum(node.left, freq) + findSum(node.right, freq) + node.val;
    	if (!freq.containsKey(sum)) {
    		freq.put(sum, 1);
    	} else {
    		freq.put(sum, freq.get(sum) + 1);
    	}
    
    	return sum;
    }
    

    }
    '''


  • 0

    Java 8 lambda flavor solution, just for your reference. Love Java but many dirty works like this sometimes, sad...

        public int[] findFrequentTreeSum(TreeNode root) {
            if (root == null) return new int[0];
            Map<Integer, Integer> map = new HashMap<>();
            dfs(root, map);
    
            int max = Collections.max(map.values(), Integer::compareTo);
            return map.entrySet().stream().
                    filter(e -> e.getValue() == max).
                        map(Map.Entry::getKey).
                            mapToInt(Integer::intValue).toArray();
        }
    
        private int dfs(TreeNode root, Map<Integer, Integer> map) {
            if (root == null) return 0;
            int sum = root.val + dfs(root.left, map) + dfs(root.right, map);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            return sum;
        }
    

  • 0
    L

    19 ms C++ DFS

        int sumTree(TreeNode* root, vector<int> &res, map<int, int> &hash, int &m){
            if(!root) return 0;
            int cur = root->val + sumTree(root->left, res,hash, m) + sumTree(root->right, res,hash, m);
            hash[cur]++;
            if(hash[cur] > m){ res.clear(); res.push_back(cur); m=hash[cur]; }
            else if(hash[cur]==m) res.push_back(cur);
            return cur;
        }
        vector<int> findFrequentTreeSum(TreeNode* root) {  // 508
            //if(!root) return vector<int>();
            vector<int> res;
            int m=INT_MIN;
            map<int, int> hash;
            sumTree(root, res, hash, m);
            return res;
        }
    

  • 0
    W
    public class Solution {
        HashMap<Integer, Integer> map = new HashMap<>();
        public int[] findFrequentTreeSum(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            
            subTreeSum(root);
            
            int max = 0;
            // need to find out the key(s) with biggest occurances(max)
            for (Integer key : map.keySet()) {
                if (map.get(key) > max) {
                    // old list is useless since key's occurance is larger
                    list = new ArrayList<>();
                    list.add(key);
                    max = map.get(key);
                }
                else if (map.get(key) == max) {
                    list.add(key);
                }
            }
            
            int[] result = new int[list.size()];
            
            for (int i = 0; i < result.length; i++) {
                result[i] = list.get(i);
            }
            
            return result;
        }
        
        public int subTreeSum(TreeNode node) {
            if (node == null) {
                return 0;
            }
            // if no child, it means it subtree sum is its value
            if (node.left == null && node.right == null) {
                map.put(node.val, map.getOrDefault(node.val, 0) + 1);
                return node.val;
            }
            
            // subTreeSum = self node value + left treesum + right tree sum
            int sum = subTreeSum(node.left) + subTreeSum(node.right) + node.val;
            map.put(sum, map.getOrDefault(sum ,0) + 1);
            
            return sum;
        }
    }
    

  • 0

    Using Java 8 on the last part.

    public int[] findFrequentTreeSum(TreeNode root) {
        maxCount = 0;
        sumToCount = new HashMap<Integer, Integer>();
        
        postOrder(root);
        
        return sumToCount.keySet().stream()
                .filter(k -> sumToCount.get(k) == maxCount)
                .mapToInt(i -> i).toArray();
    }
    

    You can even say, mapToInt(Integer::intValue).toArray();


  • 0
    F

    Same idea. But I didn't use global variable.

    class Solution {
        public int[] findFrequentTreeSum(TreeNode root) {
            HashMap<Integer, Integer> map = new HashMap();
            helper(root, map);
            List<Integer> list = new ArrayList();
            int max = 0;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int fre = entry.getValue();
                if (fre >= max) {
                    if (fre > max) {
                        list.clear();
                        max = fre;
                    }
                    list.add(entry.getKey());
                }
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i);
            }
            return res;
        }
        public int helper(TreeNode root, HashMap<Integer, Integer> map) {
            if (root == null) {
                return 0;
            }
            int left = helper(root.left, map);
            int right = helper(root.right, map);
            int sum = left + right + root.val;
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            return sum;
        }
    }
    

  • 0
    C

    12 ms TIME

    
    class Solution {
        int maxCount = 0;
        List<Integer> output = new ArrayList<Integer>();
        public int[] findFrequentTreeSum(TreeNode root) {
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            if(root==null){
                return new int[0];
            }
            
            helper(root,0,map);
            
            int[] arr = new int[output.size()];
            for(int i=0; i<output.size();i++){
                arr[i] = output.get(i);
            }
            
            return arr;
        }
        
        public int helper(TreeNode root, int currentSum,Map<Integer,Integer> map){
            if(root==null){
                return currentSum;
            }
            Integer left = null;
            Integer right = null;
            Integer complete = null;
            if(root.left!=null){
                left = helper(root.left,currentSum,map);
            }
            
            if(root.right!=null){
                right = helper(root.right,currentSum,map); 
            }
            
            //Calucating complete
            if(left!=null && right!=null){
                complete = root.val + left + right;
            }
            else if(left!=null){
                complete = root.val + left;
            }
            else if(right!=null){
                complete = root.val + right;
            }
            else {
                complete = root.val;
            }
            
    
                int count = 1;
                if(map.containsKey(complete)){
                    count = map.get(complete);
                    count = count + 1;
                }
                map.put(complete,count);
                //System.out.println("maxCount="+maxCount+ " count="+count+" complete"+complete+ " root"+root.val);
                
                if(maxCount < count){
                    output = new ArrayList<Integer>();
                    output.add(complete);
                    maxCount = count;
                }
                else{
                    if(maxCount==count){
                        output.add(complete);
                    }
                }
    
            return complete;
        }
    }```

  • 0
    C

    @Tōsaka-Rin not O(n) solution, because you did not use post-order traverse.


  • 0
    M

    An iterative way

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int[] findFrequentTreeSum(TreeNode root) {
            Map<Integer, Integer> freqs = new HashMap<>();
            Stack<TreeNode> stack = new Stack<>();
            Stack<Integer> sums = new Stack<>();
            TreeNode cur = root, pre = null;
            int preSum = 0, maxFreq = 0, maxCount = 0;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    sums.push(cur.val);
                    cur = cur.left;
                }
                TreeNode node = stack.peek();
                sums.push(sums.pop() + preSum);
                if (node.right != null && node.right != pre) {
                    preSum = 0;
                    cur = node.right;
                    continue;
                }
                pre = stack.pop();
                preSum = sums.pop();
                int freq = freqs.getOrDefault(preSum, 0) + 1;
                freqs.put(preSum, freq);
                if (freq > maxFreq) {
                    maxCount = 1;
                    maxFreq = freq;
                } else if (freq == maxFreq) {
                    maxCount++;
                }
            }
            
            int[] res = new int[maxCount];
            int i = 0;
            for (Integer subsum : freqs.keySet()) {
                int freq = freqs.get(subsum);
                if (freq == maxFreq) {
                    res[i++] = subsum;
                }
            }
    
            return res;
        }
    }
    

Log in to reply
 

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