Clean Java solution (14ms < 98.17% at the time submitted)


  • 0
    E

    recursive post order traversal, memorize using hashmap, also use a list to record the seen max occurrence of sum to avoid another round of hashmap traversal.

    public class Solution {
        public int[] findFrequentTreeSum(TreeNode root) {
          List<Integer[]> track = new ArrayList<>(); 
          Map<Integer,Integer> lookup = new HashMap<>(); 
          find(root,lookup, track); 
          int[] res = new int[track.size()];
          for (int idx = 0 ; idx < track.size(); idx ++) {
              res[idx] = track.get(idx)[1];
          }
          return res; 
        }
    
        private int find(TreeNode root, Map<Integer,Integer> lookup, List<Integer[]> track) {
            if (root == null) return 0; 
            int total = find(root.left,lookup, track) + find(root.right,lookup,track) + root.val; 
            int count = lookup.getOrDefault(total, 0) + 1;
            lookup.put(total, count);
            if (track.size() == 0 || track.get(0)[0]<= count) {
                if (track.size() > 0 && track.get(0)[0] < count) track.clear();
                track.add(new Integer[]{count,total});
            }
            return total;
        }
    }
    

Log in to reply
 

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