原文链接: https://leetcode-cn.com/problems/most-frequent-subtree-sum

英文原文

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

 

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Example 2:

Input: root = [5,2,-5]
Output: [2]

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

中文题目

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

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

 

示例 1：
输入:

  5
 /  \
2   -3

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

示例 2：
输入：

  5
 /  \
2   -5

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

 

提示： 假设任意子树元素和均可以用 32 位有符号整数表示。

通过代码

高赞题解

计算子树元素和，应该自底向上，故考虑后序遍历，遍历过程中存取每个节点为根节点的子树元素和

int dfs(unordered_map<int, int>& M, TreeNode* root) {
  if (!root) return 0;
  int left = dfs(M, root->left);
  int right = dfs(M, root->right);
  int sum = left + right + root->val;
  M[sum]++;
  return sum;
}
vector<int> findFrequentTreeSum(TreeNode* root) {
  if (!root) return {};
  vector<int> res;
  unordered_map<int, int> M;
  dfs(M, root);
  int maxTime = 0;
  for (auto item : M) maxTime = max(maxTime, item.second);
  for (auto item : M)
    if (item.second == maxTime) res.push_back(item.first);
  return res;
}

统计信息

通过次数	提交次数	AC比率
15514	22845	67.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
另一棵树的子树	简单