package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/most-frequent-subtree-sum/
 */
public class Problem508 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int[] findFrequentTreeSum(TreeNode root) {
        // TODO
        return new int[0];
    }

    public static void main(String[] args) {
        Problem508 prob = new Problem508();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(-3);
        System.out.println(Arrays.toString(prob.findFrequentTreeSum(root))); // [2, -3, 4]

        root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(-5);
        System.out.println(Arrays.toString(prob.findFrequentTreeSum(root))); // [2]
    }
}

@@ -34,17 +34,91 @@
 il.Array
-s
+List;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
 ;%0A%0A/**%0A 
@@ -436,305 +436,621 @@
     
-// TODO%0A        return
+Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        IntRef max =
  new 
-int%5B0%5D
+IntRef()
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem508 prob = new Problem508();%0A%0A        TreeNode root = new TreeNode(5);%0A        root.left = new TreeNode(2);%0A        root.right = new TreeNode(-3);%0A        System.out.println(Arrays.toString(prob.
+findFrequentTreSum(root, map, max);%0A        List%3CInteger%3E list = new ArrayList%3C%3E();%0A        for (Map.Entry%3CInteger, Integer%3E entry : map.entrySet()) %7B%0A            if (entry.getValue() == max.val) %7B%0A                list.add(entry.getKey());%0A            %7D%0A        %7D%0A        int%5B%5D result = new int%5Blist.size()%5D;%0A        for (int i = 0; i %3C result.length; i++) %7B%0A            result%5Bi%5D = list.get(i);%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static class IntRef %7B%0A        private int val;%0A    %7D%0A%0A    private static int 
 find
@@ -1064,103 +1064,185 @@
 tTre
-e
 Sum(
-root))); // %5B2, -3, 4%5D%0A%0A        root = new TreeNode(5);%0A        root.left = new TreeNode(2
+TreeNode node, Map%3CInteger, Integer%3E map, IntRef max) %7B%0A        if (node == null) %7B%0A            return 0;%0A        %7D%0A        int left = findFrequentTreSum(node.left, map, max
 );%0A 
@@ -1252,21 +1252,20 @@
     
-root.
+int 
 right = 
 new 
@@ -1264,109 +1264,425 @@
 t = 
-new TreeNode(-5);%0A        System.out.println(Arrays.toString(prob.findFrequentTreeSum(root))); // %5B2%5D
+findFrequentTreSum(node.right, map, max);%0A        int sum = node.val + left + right;%0A        if (!map.containsKey(sum)) %7B%0A            int newCount = 1;%0A            max.val = Math.max(max.val, newCount);%0A            map.put(sum, newCount);%0A        %7D else %7B%0A            int newCount = map.get(sum) + 1;%0A            max.val = Math.max(max.val, newCount);%0A            map.put(sum, newCount);%0A        %7D%0A        return sum;
 %0A   

Solve problem 508