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

曾经终败给现在 2022-12-24 00:39 106阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

/**
     * 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;
        }
    }

![在这里插入图片描述][20201125202604972.png_pic_center]

[508.]: https://leetcode-cn.com/problems/most-frequent-subtree-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/23c4d9bb727249149a3b03fbe183f965.png
[20201125202604972.png_pic_center]: https://img-blog.csdnimg.cn/20201125202604972.png#pic_center