【坚持每日一题8.23】508. 出现次数最多的子树元素和

给你一个二叉树的根结点,请你找出出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的子树元素和(不限顺序)。

示例 1:
输入:

5
/
2 -3
返回 [2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。

示例 2:
输入:

5
/
2 -5
返回 [2],只有 2 出现两次,-5 只出现 1 次。

提示: 假设任意子树元素和均可以用 32 位有符号整数表示。

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 {
    
    private Map<Integer, Integer> sumCount = new HashMap<>();
    private Integer maxFrequent = Integer.MIN_VALUE;
    
    public int[] findFrequentTreeSum(TreeNode root) {
        
        postOrder(root);
        
        List<Integer> help = new ArrayList<>();
        
        // 将符合条件的所有元素和添加到 help list 当中
        for (Map.Entry<Integer, Integer> next : sumCount.entrySet()) {
            
            // 添加计数等于最大次数 maxFrequent 的 元素和
            if (next.getValue() == maxFrequent) {
                help.add(next.getKey());
            }
        }
        
        int[] res = new int[help.size()];
        
        for (int i = 0; i < help.size(); i++) {
            res[i] = help.get(i);
        }
        
        return res;
    }
    
    private int postOrder(TreeNode node) {
        
        // 当节点为 null, 它的元素和等于 0, 利于它的父节点进行元素和统计
        if (node == null) {
            return 0;
        }
        
        int left = postOrder(node.left);
        int right = postOrder(node.right);
        
        int sum = left + right + node.val;
        
        int value = sumCount.getOrDefault(sum, 0);
        
        sumCount.put(sum, value + 1);
        
        maxFrequent = Math.max(maxFrequent, value + 1);
        
        return sum;
        
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容