出现次数最多的子树元素和 图解题解

每个子树都有一个和，要数哪个和最常见

给一棵二叉树，每个节点都能框出一棵以它为根的子树；把这棵子树里所有节点值加起来，就是这个节点的子树和。叶子也算一棵子树，它的和就是自身那个值。全树 n 个节点凑出 n 个子树和，其中难免有重复。题目问的是：哪些子树和出现的次数最多，把它们全都返回，顺序不限。题面例子 root=[5,2,-3]，三个节点各给一个和，答案是 [2,-3,4]。

对每个节点各扫一遍子树求和，n 大了就吃力

求一个节点的子树和，得把它底下整棵子树都加一遍。可要是每个节点都各自这么加一次，靠上的节点会重复走下面一大片：根节点扫全树、根的两个孩子又各扫自己那半，同一个叶子被反复加进它每一个祖先的和里。n 个节点最坏叠到 O(n²) 量级的重复遍历，节点一多就慢得明显。

父亲的和等着孩子先算出来

重复全出在一件事上：父节点的和，等于它自己的值，加左子树的和，再加右子树的和。也就是说孩子的子树和只要算一次，父亲拿来直接用就行，用不着重新下去扫一遍。这就要求处理顺序是先孩子后父亲——两个孩子的和都递归求出来了，父节点才拿着它们把自己这棵子树的和拼起来，这种走法叫后序遍历。每个节点只在轮到自己时被加一次，重复就没了。

递归返回子树和，哈希表边算边记一笔

让递归函数 dfs 干两件事：算出当前节点的子树和 s = 节点值 + dfs(左) + dfs(右)，并把 s 返回给父亲；同时在一张按值计数的哈希表 cnt 里给 s 记一笔，也就是 cnt[s] 加一。空节点返回 0，正好当作递归到底的边界。

整棵树跑完，cnt 里存的就是每个子树和各出现了几次。取其中最大的次数 best，再把所有出现次数正好等于 best 的和收集起来，就是答案。这里要当心可能有好几个和并列 best，得一个不落全返回。

拿题面的 root=[5,2,-3] 从叶子算到根

这棵树三个节点：根 5，左孩子 2，右孩子 -3，两个孩子都是叶子。后序先下到左孩子 2，它没有孩子，dfs(左)、dfs(右) 都返回 0，子树和 s = 2 + 0 + 0 = 2，cnt[2] 记 1。再到右孩子 -3，同样是叶子，s = -3，cnt[-3] 记 1。最后回到根 5，它的和 s = 5 + 2 + (-3) = 4，cnt[4] 记 1。三个和 2、-3、4 各出现 1 次，最大次数 best = 1，于是三个都是答案，顺序不限，题面给的就是 [2,-3,4]。

写成前序就全错，还有两个必踩的坑

最致命的是遍历顺序：把后序写成前序或层序，父亲还没拿到孩子的和就抢先结算，得到的全是错值。另一个坑是只返回出现次数最多的那一个和——本题并列第一很常见，漏掉几个直接判错。还有别忘了叶子也是一棵子树，它的和就是自身，同样要记进 cnt，少记这一笔次数就可能数偏。

复杂度上，后序把每个节点访问、结算恰好一次，记哈希和最后扫表都是均摊 O(1)，时间 O(n)。空间看两处：哈希表最多存 n 个不同的和，递归栈深等于树高，链状树最坏也到 O(n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        cnt = Counter()
        def dfs(node):
            if not node:
                return 0
            s = node.val + dfs(node.left) + dfs(node.right)
            cnt[s] += 1
            return s
        dfs(root)
        if not cnt:
            return []
        best = max(cnt.values())
        return sorted([s for s, c in cnt.items() if c == best])

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> cnt;
        function<int(TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) return 0;
            int s = node->val + dfs(node->left) + dfs(node->right);
            ++cnt[s];
            return s;
        };
        dfs(root);
        int best = 0;
        for (auto& [_, c] : cnt) best = max(best, c);
        vector<int> ans;
        for (auto& [s, c] : cnt) if (c == best) ans.push_back(s);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

Java

import java.util.*;
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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Map<Integer, Integer> cnt;
    public int[] findFrequentTreeSum(TreeNode root) {
        cnt = new HashMap<>();
        dfs(root);
        int best = 0;
        for (int c : cnt.values()) best = Math.max(best, c);
        ArrayList<Integer> ans = new ArrayList<>();
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) if (e.getValue() == best) ans.add(e.getKey());
        Collections.sort(ans);
        int[] out = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) out[i] = ans.get(i);
        return out;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int s = node.val + dfs(node.left) + dfs(node.right);
        cnt.put(s, cnt.getOrDefault(s, 0) + 1);
        return s;
    }
}