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

这道题到底在问什么

输入

root=[5,2,-3]

输出

[2,-3,4]（三个和各出现 1 次，全是最多）

最优解：一步一步想明白

1. 3记住这条主线：先下钻到叶子，再自底向上结算每个子树和，边算边往哈希表记一笔。
2. 4栈空，哈希表空开局哈希表是空的。后序 DFS 从根节点 50 出发，先一路下钻到最左下的叶子，再自底向上一个个结算子树和。盯住右边这张计数表，它会随着结算逐行长出来。
3. 5进入 50递归进入节点 50（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
4. 6进入 20递归进入节点 20（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
5. 7进入 30递归进入节点 30（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
6. 8叶子 10递归走到节点 10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
7. 9子树和 = 10节点 10 的左右子树和都齐了，结算：子树和 = 10。把 10 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
8. 10叶子 40递归走到节点 40（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
9. 11子树和 = 40节点 40 的左右子树和都齐了，结算：子树和 = 40。把 40 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
10. 12子树和 = 30 + 10 + 40 = 80节点 30 的左右子树和都齐了，结算：子树和 = 30 + 10 + 40 = 80。把 80 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
11. 13叶子 -10递归走到节点 -10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
12. 14子树和 = (-10)节点 -10 的左右子树和都齐了，结算：子树和 = (-10)。把 -10 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
13. 15子树和 = 20 + 80 + (-10) = 90节点 20 的左右子树和都齐了，结算：子树和 = 20 + 80 + (-10) = 90。把 90 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
14. 16进入 80递归进入节点 80（紫色）。它还有孩子，子树和现在算不了，得先把左右孩子的子树和都求出来，所以继续往下钻。
15. 17叶子 40递归走到节点 40（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
16. 18子树和 = 40节点 40 的左右子树和都齐了，结算：子树和 = 40。把 40 记进哈希表，这个和之前出现过，计数涨到 2。节点变绿表示已经处理完。
17. 19叶子 10递归走到节点 10（紫色），它没有孩子，是叶子。叶子的子树就是它自己一个人，下一帧直接结算。
18. 20子树和 = 10节点 10 的左右子树和都齐了，结算：子树和 = 10。把 10 记进哈希表，这个和之前出现过，计数涨到 2。节点变绿表示已经处理完。
19. 21子树和 = 80 + 40 + 10 = 130节点 80 的左右子树和都齐了，结算：子树和 = 80 + 40 + 10 = 130。把 130 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
20. 22子树和 = 50 + 90 + 130 = 270节点 50 的左右子树和都齐了，结算：子树和 = 50 + 90 + 130 = 270。把 270 记进哈希表，它是第一次出现，计数记 1。节点变绿表示已经处理完。
21. 23最大次数 = 2九个节点全部结算完，计数表也满了。现在扫一遍这张表，找出现次数最大的那个。可以看到 10 和 40 都出现了 2 次，其余的和都只出现 1 次，所以最大次数是 2。
22. 24答案 = [10, 40]次数等于 2 的和有两个：10 和 40，它俩并列最多。题目要求把出现次数最多的和全部返回，所以答案是 [10, 40]。这也提醒我们：最多的可能不止一个，别只返回一个就交卷。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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])

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问