Java O(n) solution


  • 0
    S
        
        Map<Integer, Integer> map = new HashMap<>();
        
        public int[] findFrequentTreeSum(TreeNode root) {
            updateSumTree(root);
            List<Integer> ans = new ArrayList<>();
            int max = 0;
            
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int count = entry.getValue();
                if (count == max) 
                    ans.add(entry.getKey());
                if (count > max) {
                    max = count;
                    ans = new ArrayList<>();
                    ans.add(entry.getKey());
                }
            }
            
            int[] result = new int[ans.size()];
            for (int i = 0;i<result.length;i++)
                result[i] = ans.get(i);
            
            return result;
        }
        
        public void updateSumTree(TreeNode root) {
            if (root == null)
                return;
            if (root.left != null) {
                updateSumTree(root.left);
                root.val += root.left.val;
            }
            if (root.right != null) {
                updateSumTree(root.right);
                root.val += root.right.val;
            }
            
            Integer count = map.get(root.val);
            if (count == null)
                map.put(root.val, 1);
            else
                map.put(root.val, count + 1);
        }
    }

Log in to reply
 

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