Add one more loop to improve performance


  • 0
    W

    My solution is similar to most of the solutions here. I found that using one more loop helped the performance quite a bit especially if the tree is huge with repeated sums. Instead of counting the max frequency in the recursion tree, I use one more loop to figure that out. I think the performance improvement results from the fact that the Keyset is much smaller than the recursion tree. In the tree, we would have to do Math.max() for every node. But of course, my code is slightly more verbose.

     private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
     public int[] findFrequentTreeSum(TreeNode root) {
            helper(root);
            int maxFreq = -1;
            for(Integer key : map.keySet()){
            	maxFreq = Math.max(maxFreq, map.get(key));
            }
            List<Integer> list = new ArrayList<Integer>();
            for(Integer key : map.keySet()){
            	if(map.get(key) == maxFreq){
            		list.add(key);
            	}
            }
            
            int[] res = new int[list.size()];
            for(int i = 0; i <res.length ; i++){
            	res[i] = list.get(i);
            }
            return  res;
            
     }
     
     
     private int helper(TreeNode node){
    	   if(node == null) return 0;
    	   int sum = node.val + helper(node.left) + helper(node.right);
    	   map.put(sum,  map.getOrDefault(sum, 0)+1);
    	   return sum;
     }

Log in to reply
 

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