LeetCode 508. 出现次数最多的子树元素和（递归）

最新推荐文章于 2022-11-07 12:10:20 发布

Michael阿明

最新推荐文章于 2022-11-07 12:10:20 发布

阅读量788

点赞数 4

分类专栏： LeetCode

本文链接：https://blog.csdn.net/qq_21201267/article/details/105715277

版权

LeetCode 专栏收录该内容

1849 篇文章

订阅专栏

本文介绍了一种在二叉树中查找出现频率最高的子树元素和的方法。通过自底向上的递归算法，计算每个节点的子树和，并使用哈希表记录各子树和的出现次数。最终，返回出现次数最多的子树和，适用于LeetCode题目。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 题目

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

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

示例 1：
输入:
  5
 /  \
2   -3
返回 [2, -3, 4]，所有的值均只出现一次，以任意顺序返回所有值。

示例 2：
输入：
  5
 /  \
2   -5
返回 [2]，只有 2 出现两次，-5 只出现 1 次。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/most-frequent-subtree-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

自底向上，计算每个节点的子树和，存入哈希map，同时记录最大出现次数
遍历哈希map取出最大次数的值

class Solution {
	unordered_map<int,int> m;
	vector<int> ans;
	int maxCount = 0;
	int s;
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        sumof(root);
        for(auto& mi : m)
        	if(mi.second == maxCount)
        		ans.push_back(mi.first);
        return ans;
    }

    int sumof(TreeNode* root)
    {
    	if(root == NULL)
    		return 0;
    	int l = sumof(root->left);//自底向上
    	int r = sumof(root->right);
    	s = l+r+root->val;
    	if(++m[s] > maxCount)
    		maxCount = m[s];
    	return s;
    }
};