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

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

题目

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

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

示例 1：
输入:

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

示例 2：
输入：

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

方法

我们用一个哈希表记录每一个可能的和出现的次数。哈希表的key为所有可能的子树元素和的值，value为该值出现的次数。

在深度优先遍历树的过程中，不仅要计算各个子树的元素和。还要根据计算出来的和值更新哈希表和最多出现的次数。

如果当前和值出现的次数为max，那么将其加入列表res。如果当前和值出现的次数大于max，那么需要先将res清空，再将当前的和值加入。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    //用一个哈希表记录每个和出现的次数
    private Map<Integer, Integer> map = new HashMap<>();
    //max为最多出现的次数
    private int max = 0;
    //用一个列表记录出现max次的和值
    private List<Integer> res = new ArrayList<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        if(root == null)
            return new int[0];
        valSum(root);
        int[] result = new int[res.size()];
        for(int i = 0; i < res.size(); i++)
            result[i] = res.get(i);
        return result;
    }

    //求以root为根节点的树的所有元素的和
    public int valSum(TreeNode root){
        if(root == null)
            return 0;
        int L = valSum(root.left);
        int R = valSum(root.right);
        int sum = root.val + L + R;
        if(!map.containsKey(sum))
            map.put(sum, 1);
        else
            map.put(sum, map.get(sum) + 1);
        if(map.get(sum) > max){
            res.clear();
            res.add(sum);
        }
        if(map.get(sum) == max)
            res.add(sum);
        max = Math.max(max, map.get(sum));
        return sum;
    }
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)