【LeetCode】出现次数最多的子树元素和 Java 题解

2022 年 6 月 20 日
本文字数：1186 字
阅读完需：约 4 分钟

题目描述

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：
输入: root = [5,2,-3]输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5]输出: [2]
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/most-frequent-subtree-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是二叉树相关的题目，解决这类题目，我们通常需要对树进行整体的遍历。题目关键点 1. 子树元素和，以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。2. 求出现次数最多的和。
首先，我们求解子树元素和，就是对二叉树进行深度优先搜索，从根节点开始，遍历到子节点，然后进行求和。
每个节点求和完成之后，我们使用 hashMap 记录每一个的数值和出现的频次。然后求出最大出现的频次并返回结果。实现代码如下，供参考。

通过代码

/** * 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 {    public int[] findFrequentTreeSum(TreeNode root) {        Map<Integer, Integer> cntMap = new HashMap<>();        dfs(root, cntMap);        int maxSize = 0;        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {            maxSize = Math.max(maxSize, entry.getValue());        }
        Set<Integer> set = new HashSet<>();        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {            if (maxSize == entry.getValue()) {                set.add(entry.getKey());            }        }
        int n = set.size();        int[] ans = new int[n];        int i = 0;        for (Integer item : set) {            ans[i++] = item;        }                return ans;    }
    private int dfs(TreeNode node, Map<Integer, Integer> map) {        if (node == null) {            return 0;        }
        int tempSum = node.val + dfs(node.left, map) + dfs(node.right, map);        map.put(tempSum, map.getOrDefault(tempSum, 0) + 1);
        return tempSum;    }   }