# 12ms Java, beat 99.77%, using ArrayList/Array to store/sort sums for each node

• The submission is 12ms and beating 99.77%. But given Arrays.sort()'s O(nlogn) complexity, i don't see why it can beat other solutions using HashMap in terms of complexity.

My solution stored sum of each node directly into a ArrayList during Post Order traversal. Later the arraylist of sums are transformed into Array which can then be sorted (O(nlogn)) and aggregated.

'''
public class Solution {
public int[] findFrequentTreeSum(TreeNode root) {
if (root == null) return new int[0];

``````    ArrayList<Integer> sums = new ArrayList<Integer>();
getAllSums(root, sums);

return findMostFrequentSums(sums);
}

/*
* recursive find sums for each node.
*/
public int getAllSums(TreeNode n, ArrayList<Integer> sums){
if (n == null) return 0;

int currSum = n.val + getAllSums(n.left, sums) + getAllSums(n.right, sums);
//System.out.println("n.val =" + n.val + ", currSum= " + currSum);
return currSum;
}

public int[] findMostFrequentSums(ArrayList<Integer> sums){

//System.out.println(" sums = " + sums);
int[] sortedSums = toIntArray(sums);
Arrays.sort(sortedSums);
//System.out.println(" sorted = " +  Arrays.toString(sortedSums));
int maxFrequence = -1;
int currSum = sortedSums[0];
int currFrequence = 1;

ArrayList<Integer> tiedSums= new ArrayList<Integer>();
for (int i = 1; i < sortedSums.length ; i++){

if (sortedSums[i] != currSum) {
if (currFrequence > maxFrequence) { // find new most frequence sum
maxFrequence = currFrequence;
tiedSums.clear();

} else if (currFrequence == maxFrequence){ // find another sum also has max frequence
}
currSum = sortedSums[i];
currFrequence = 1;
} else {
currFrequence ++;
}
}
if (currFrequence > maxFrequence) {
tiedSums.clear();
} else if (currFrequence == maxFrequence){
}
}

public int[] toIntArray(ArrayList<Integer> sums){
int[] res = new int[sums.size()];
for (int i = 0; i < sums.size(); i++){
res[i] = (int) sums.get(i);
}
return res;
}
``````

}
''''

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