Java 2 hashmaps solution


  • 0
    J
    public class Solution {
        private int max = 0;
        
        public int[] findFrequentTreeSum(TreeNode root) {
            if (root == null) return new int[0];
            HashMap<Integer, Integer> freq = new HashMap<>();
            HashMap<Integer, Set<Integer>> revFreq = new HashMap<>();
            count(root, freq, revFreq);
            Set<Integer> ns = revFreq.get(max);
            int[] res = new int[ns.size()];
            int idx = 0;
            Iterator<Integer> it = ns.iterator();
            while (it.hasNext()) {
                res[idx] = it.next();
                idx++;
            }
            return res;
        }
        
        private int count(TreeNode root, HashMap<Integer, Integer> freq, HashMap<Integer, Set<Integer>> revFreq) {
            if (root == null) return 0;
            int ls = root.left == null ? 0 : count(root.left, freq, revFreq);
            int rs = root.right == null ? 0 : count(root.right, freq, revFreq);
            int sum = ls + rs + root.val;
            Integer f = freq.get(sum);
            if (f == null) f = 0;
            freq.put(sum, f + 1);
            if (f > 0) {
                Set<Integer> oldSet = revFreq.get(f);
                if (oldSet != null) oldSet.remove(sum);
            } 
            Set<Integer> newSet = revFreq.get(f + 1);
            if (newSet == null) {
                newSet = new HashSet<>();
                revFreq.put(f + 1, newSet);
            }
            newSet.add(sum);
            if (max < f + 1) max = f + 1;
            return sum;
        }
    }
    

Log in to reply
 

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