Java solution DFS with Hashmap / T : O(N), S : O(1)


  • 0
    J
    public class Solution {
        public int[] findFrequentTreeSum(TreeNode root) {
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            sumdfs(root, map);
            int max = Integer.MIN_VALUE;
            int count = 0;
            for(int key : map.keySet()){
                if(max < map.get(key)){
                    max = map.get(key);
                    count = 1;
                }
                else if(max == map.get(key)){
                    count++;
                } 
            }
            
            int[] result = new int[count];
            count = 0;
            for(int key : map.keySet()){
                if(max == map.get(key)){
                    result[count++] = key;
                }
            }
            return result;
        }
        
        public int sumdfs(TreeNode root, HashMap<Integer, Integer> map){
            if(root == null) return 0;
            int leftsum = sumdfs(root.left, map);
            int rightsum = sumdfs(root.right, map);
            
            int sum = leftsum + rightsum + root.val;
            if(map.containsKey(sum)){
                map.put(sum, map.get(sum) + 1);
            }
            else{
                map.put(sum, 1);
            }
            return sum;
        }
    }
    

  • 0
    J

    T : O(N), S : O(N)


Log in to reply
 

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