Java Solution Using HashMap, runtime beats 99%


  • 0
    A
    public class Solution {
        
        Map<Integer, Integer> map = new HashMap();
        List<Integer> list = new ArrayList();
        int freq = 1;
        public int[] findFrequentTreeSum(TreeNode root) {
            helper(root);
            int[] result = new int[list.size()];
            for(int i=0;i<list.size();i++) {
                result[i] = list.get(i);
            }
            return result;
        }
        
        public void helper(TreeNode root) {
            if(root == null) {
                return;
            }
            helper(root.left);
            helper(root.right);
            if(root.left != null) {
                root.val += root.left.val;
            }
            if(root.right != null) {
                root.val += root.right.val;
            }
            updateList(root);
        }
        
        public void updateList(TreeNode root) {
            if(root == null) {
                return;
            }
            if(!map.containsKey(root.val)) {
                map.put(root.val, 1);
                if(freq == 1) {
                    list.add(root.val);
                }
            } else {
                map.put(root.val, map.get(root.val) + 1);
                if(map.get(root.val) > freq) {
                    freq = map.get(root.val);
                    list.clear();
                    list.add(root.val);
                } else if(map.get(root.val) == freq) {
                     list.add(root.val);
                }
            }
        }
        
    }

Log in to reply
 

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