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

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxC = 0; // 记录和的 最大个数
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) { // null
            return new int[0];
        }
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        sum(root, map); 
        List<Integer> res = new LinkedList<>(); 

        for (int i: map.keySet()) {
            if (map.get(i) == maxC) { // 将max对应的key 加入
                res.add(i); 
            }
        } 
        int[] result = new int[res.size()]; 
        for (int i = 0; i < res.size(); i ++) {
            result[i] = res.get(i);
        }
        return result;
    }
    
    public int sum(TreeNode root,Map<Integer,Integer> map) { 
        if (root == null) { return 0; }
        int sum = (root.val + sum(root.left, map) + sum(root.right, map));
        if (map.containsKey(sum)) {// 如果mapsum存在, 则+ 1, 反之 为1)
            map.put(sum, map.get(sum) + 1);
        }else {
            map.put(sum, 1);
        }
        maxC = Math.max(maxC, map.get(sum)); // 迭代maxC
        return sum;
    }
    
}