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

2026-09-13 HGNULB 约 5 分钟

文章信息 2 个分类 4 个标签

分类

LeetCode 中等

题目描述

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

题意分析

每个节点都对应一棵以它为根的完整子树，子树元素和包含这个节点以及全部后代。统计这些和值各出现多少次，返回所有达到最高频次的和值，顺序不限。

不同子树即使结构、节点值不同，也可能具有相同的和，需要合并计数。节点值允许为负，不能只统计正和值。TreeNode 由平台提供。

解法：逆序处理父先子后的节点列表

核心思路

[!blue]

当前节点的子树和等于“节点值 + 左子树和 + 右子树和”。要计算父节点，必须先得到孩子的结果，但左右孩子之间不需要固定先后顺序。

先从根开始收集节点：每处理列表中的一个节点，就把它的非空孩子追加到末尾，并继续处理后来追加的节点。这样每个父节点一定早于它的孩子出现。再倒着扫描列表，孩子就一定先于父节点被计算，满足子树和的全部依赖。

用 sums 按节点引用保存已经算出的子树和，空孩子贡献 0；用 counts 按数值统计每个和值的频次。两个映射职责不同：前者提供父节点需要的孩子结果，后者把不同子树的相同和值合并。

每算出一个节点的和，就把对应频次加一并更新最高频次 best。所有节点处理完成后，再遍历频次表，取出计数等于 best 的全部键。每个节点恰好贡献一次子树，因此不会漏计或重计。

解题步骤

将根节点放入列表，按不断增长的列表长度向后遍历，依次追加左右孩子。

创建节点到子树和的映射、和值到频次的映射，将最高频次设为 0。

从列表末尾向前处理节点，用已保存的左右子树和加上当前值，得到当前子树和。

保存当前节点的结果，将该和值的计数加一，并更新最高频次。

遍历频次表，收集所有最高频和值。代码也为传入空根时保留了返回空结果的边界处理。

代码实现

class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        List<TreeNode> nodes = new ArrayList<>();

        nodes.add(root);

        for (int i = 0; i < nodes.size(); i++) {
            TreeNode node = nodes.get(i);

            if (node.left != null) {
                nodes.add(node.left);
            }

            if (node.right != null) {
                nodes.add(node.right);
            }
        }

        Map<TreeNode, Integer> sums = new HashMap<>();
        Map<Integer, Integer> counts = new HashMap<>();
        int best = 0;

        for (int i = nodes.size() - 1; i >= 0; i--) {
            TreeNode node = nodes.get(i);
            int sum = node.val + sums.getOrDefault(node.left, 0) + sums.getOrDefault(node.right, 0);

            sums.put(node, sum);
            int count = counts.merge(sum, 1, Integer::sum);

            best = Math.max(best, count);
        }

        List<Integer> answer = new ArrayList<>();

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == best) {
                answer.add(entry.getKey());
            }
        }

        int[] out = new int[answer.size()];

        for (int i = 0; i < out.length; i++) {
            out[i] = answer.get(i);
        }

        return out;
    }
}

func findFrequentTreeSum(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    nodes := []*TreeNode{
        root,
    }
    for i := 0; i < len(nodes); i++ {
        node := nodes[i]
        if node.Left != nil {
            nodes = append(nodes, node.Left)
        }
        if node.Right != nil {
            nodes = append(nodes, node.Right)
        }
    }
    sums, counts := map[*TreeNode]int{}, map[int]int{}
    best := 0
    for i := len(nodes) - 1; i >= 0; i-- {
        node := nodes[i]
        sum := node.Val + sums[node.Left] + sums[node.Right]
        sums[node] = sum
        counts[sum]++
        best = max(best, counts[sum])
    }
    answer := []int{}
    for sum, count := range counts {
        if count == best {
            answer = append(answer, sum)
        }
    }
    return answer
}

复杂度分析

时间复杂度：期望 $O(n)$，收集节点、逆序计算和筛选最高频各为线性，单次哈希操作按平均常数时间计算。

空间复杂度：$O(n)$，节点列表、节点子树和及和值频次表都最多保存线性数量的条目。

关键点总结

[!green]

父先子后的列表逆序后就是合法计算顺序，关键是孩子先完成，不要求左右子树的固定顺序。

节点映射记录单棵子树的结果，频次映射记录各个和值出现的次数。

显式保存节点列表完成依赖排序，不需要依赖递归调用栈。

易错点总结

[!yellow]

统计的是整棵子树的和，不是节点值，也不是从根到某个节点的路径和。

正向计算时孩子结果可能尚不存在，必须在列表收集完成后逆序处理。

最高频可能由多个不同和值并列获得，需要全部返回，而不是只记录最后一次更新的和值。

频次表按和值作为键，节点结果表按节点引用作为键，不能把两种映射混用。

相似题目

题目	难度	关联与区别
250. 统计同值子树	中等	都先汇总孩子状态再判断当前子树；本题汇总数值，同值子树汇总布尔条件。
1120. 子树的最大平均值	中等	两题都后序求出完整子树的节点值总和；本题用哈希表累计各子树和的频次，该题再累计节点数以比较子树平均值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/42547465

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！