Java recursion O(n)


  • 0
     /*
        use a hashmap to store sum - frequency
        priority queue to store rank
        recursively traverse each node and put their sum in hashmap and queue:
        sum(node):
            if node == null: return 0
            int sum = node.val + sum(node.left) + sum(node.right)
            map put (sum, map.get(sum) + 1)
            return sum
     */
    public class Solution {
        Map<Integer, Integer> map = new HashMap<>();
        
        public int[] findFrequentTreeSum(TreeNode root) {
            sum(root);
            List<Integer> result = new ArrayList<>();
            int max = 0;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                max = Math.max(entry.getValue(), max);
            }
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (max == entry.getValue()) result.add(entry.getKey());
            }
            int[] array = new int[result.size()];
            for (int i = 0; i < result.size(); i += 1) array[i] = result.get(i);
            return array;
        }
        
        public int sum(TreeNode node) {
            if (node == null) return 0;
            int sum = node.val + sum(node.left) + sum(node.right);
            if (map.containsKey(sum)) map.put(sum, map.get(sum) + 1);
            else map.put(sum, 1);
            return sum;
        }
    }
    
    

Log in to reply
 

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