[刷题防痴呆] 0508 - 出现次数最多的子树元素和 (Mos

题目地址

https://leetcode.com/problems/most-frequent-subtree-sum/

题目描述

508. Most Frequent Subtree Sum

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

 

Example 1:


Input: root = [5,2,-3]
Output: [2,-3,4]
Example 2:


Input: root = [5,2,-5]
Output: [2]

思路

• 递归 + hashmap.
• 递归对每个subtree的sum进行计数.
• hashmap中存储每一个sum对应的count.
• 递归结束后统计输出最多count的sum list.

关键点

代码

• 语言支持：Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        dfs(root);
        int maxCount = 0;
        for (int key: map.keySet()) {
            maxCount = Math.max(map.get(key), maxCount);
        }
        List<Integer> list = new ArrayList<>();
        for (int key: map.keySet()) {
            if (map.get(key) == maxCount) {
                list.add(key);
            }
        }
        int[] res = new int[list.size()];
        int index = 0;
        for (int num: list) {
            res[index++] = num; 
        }
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        int sum = node.val + left + right;
        map.put(sum, map.getOrDefault(sum, 0) + 1);

        return sum;
    }
}