Short Easy Java


  • 9
    public class Solution {
        int max = 0;
        public int[] findFrequentTreeSum(TreeNode root) {
            if(root==null) return new int[0];
            Map<Integer, Integer> map = new HashMap<>();
            helper(root, map);
            List<Integer> res = new LinkedList<>();
            for(Map.Entry<Integer, Integer> me: map.entrySet()){
                if(me.getValue()==max) res.add(me.getKey());
            }
            return res.stream().mapToInt(i->i).toArray();
        }
        
        private int helper(TreeNode n, Map<Integer, Integer> map){
            int left = (n.left==null) ? 0 : helper(n.left, map);
            int right = (n.right==null) ? 0 : helper(n.right, map);
            int sum = left + right + n.val;
            map.put(sum, map.getOrDefault(sum,0)+1);
            max = Math.max(max, map.get(sum));
            return sum;
        }
    }
    

  • 0

    I have a question about "helper" method. Because this method has a return value, can we just write helper() in one single line? thx~


  • 0

    @simplexp
    Yes, you can.
    Writing in a single line means you just call that function but you do not need a return value.


  • 0
    I

    @Chidong Awesome Solution!


  • 0
    X

    Good solution. A bit improvement:

        public int[] findFrequentTreeSum(TreeNode root) {
            final Map<Integer, Integer> occurMap = new HashMap<>(); // key is sum, value is the occurences of the sum.
            sum(root, occurMap);
            int maxOccurs = occurMap.values().stream().max(Comparator.naturalOrder()).orElse(-1);
            return occurMap.entrySet().stream().filter(e -> e.getValue() == maxOccurs).mapToInt(e -> e.getKey()).toArray();
        }
    
        private int sum(TreeNode root, Map<Integer, Integer> occurMap) {
            if (root == null) return 0;
            int sum = root.val + sum(root.left, occurMap) + sum(root.right, occurMap);
            occurMap.compute(sum, (k, v) -> v == null ? 1 : v + 1);
            return sum;
        }
    

  • 2
    Y

    @Chidong

    return res.stream().mapToInt(i->i).toArray(); is very very slow.


  • 0
    Z

    @yoli could you give more details on why it is really slow?


  • 0

    @zjiang90 I tried the exact trick. With this stream trick, the submission time is 95ms and 97ms(two submission), without it, 17ms. This is concise but actually not so fast.


  • 0
    D

    Without using global variable

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

Log in to reply
 

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