0508. Most Frequent Subtree Sum
===============================
题目信息
--------
:题号: 0508
:难度: Medium
:主题: 二叉树、子树元素和、频率统计、并列结果
:原题: `LeetCode 0508 `_
:重点: 每个节点都定义一棵以其为根的子树、子树和包含全部后代、返回所有最高频率的和且顺序不限
题目重述
--------
给定一棵非空二叉树。对树中的每个节点,计算以该节点为根的整棵子树中所有节点值之和;不同节点即使得到相同的和,也分别贡献一次出现次数。
返回出现频率最高的所有子树和。若多个和并列最高,需要全部返回,顺序不限。节点值和子树和都可能为负数。
自建示例
--------
某个子树和重复出现:
.. code-block:: text
输入:root = [0,1,1]
输出:[1]
解释:两个叶节点对应的子树和都为 1,根节点对应的子树和为 2,因此 1 的频率最高。
所有子树和频率相同:
.. code-block:: text
输入:root = [3,1,-1]
输出:[1,-1,3]
解释:两个叶子的子树和分别为 1 和 -1,整棵树的和为 3,三者都只出现一次,因此都应返回,顺序不限。
后序计算子树和并累计频率
------------------------
节点的子树和必须等左右子树都已知道,因此用后序递归返回 ``leftSum + rightSum + node->val``。每得到一个子树和就增加其频率并更新最高频率;遍历结束后再收集所有达到最高频率的和。
子树和可能为负数,哈希表键使用 ``long long``;不同节点产生相同和时,频率仍按节点次数累加。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::unordered_map frequency;
int bestFrequency = 0;
long long sum(TreeNode* node) {
if (node == nullptr) return 0;
long long total = node->val + sum(node->left) +
sum(node->right);
bestFrequency = std::max(bestFrequency, ++frequency[total]);
return total;
}
public:
std::vector findFrequentTreeSum(TreeNode* root) {
frequency.clear();
bestFrequency = 0;
sum(root);
std::vector result;
for (const auto& [value, count] : frequency) {
if (count == bestFrequency) {
result.push_back(static_cast(value));
}
}
return result;
}
};
代码分析
--------
后序返回值确保每个节点的和包含全部后代,哈希频率确保并列结果不会遗漏。每个节点只计算一次,时间复杂度为 ``O(n)``(平均哈希),递归栈和频率表空间为 ``O(n)``。