15ms O(n) Accepted Solution. Beats 96.10%


  • 0
    C

    Any suggestions for improvement are welcome.

    public class Solution {
        int maxCount = 0;
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        
        public int[] findFrequentTreeSum(TreeNode root) {
            sum(root);
            int[] arr = new int[res.size()];
            int idx = 0;
            for (int i : res) arr[idx++] = i;
            return arr;
        }
        
        public int sum(TreeNode root) {
            if (root == null) return 0;
            int left = sum(root.left), right = sum(root.right);
            int sum = left + right + root.val;
            
            int currCount = map.getOrDefault(sum, 0) + 1;
            map.put(sum, currCount);
            
            if (currCount == maxCount) res.add(sum);
            else if (currCount > maxCount) {
                res.clear();
                res.add(sum);
                maxCount = currCount;
            }
            
            return sum;
        }
    }
    

Log in to reply
 

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