508. 出现次数最多的子树元素和

题目来源

508. 出现次数最多的子树元素和

题目描述

在这里插入图片描述

题目解析

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
private int maxCount = 0;
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public int[] findFrequentTreeSum(TreeNode root) {
        helper(root);
        LinkedList<Integer> list = new LinkedList<>();
        for (Integer key : map.keySet() ){
            if (map.get(key) == maxCount){
                list.add(key);
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            ints[i] = list.get(i);
        }
        return ints;
    }
    private int helper(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        root.val = root.val + left + right;
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        maxCount = Math.max(maxCount, map.get(root.val));
        return root.val;
    }
}