木又连续日更第93天(93/100)
木又的第137篇leetcode解题报告
二叉树
类型第27篇解题报告
leetcode第508题:出现次数最多的子树元素和
https://leetcode-cn.com/problems/most-frequent-subtree-sum/
【题目】
给出二叉树的根,找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的元素(不限顺序)。
示例 1
输入:
5
/ \
2 -3
返回 [2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。
示例 2
输入:
5
/ \
2 -5
返回 [2],只有 2 出现两次,-5 只出现 1 次。
提示:假设任意子树元素和均可以用 32 位有符号整数表示。
【思路】
本题和【T136-二叉搜索树中的众数】比较类似,递归遍历得到子树元素和,放入字典(map)中,再找到字典中出现次数最大的元素。
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findFrequentTreeSum(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
self.d = {}
self.get_sum(root)
max_count = max(self.d.values())
res = list(map(lambda x: x[0], filter(lambda x: x[1] == max_count, self.d.items())))
return res
def get_sum(self, node):
if not node:
return 0
val = node.val + self.get_sum(node.left) + self.get_sum(node.right)
self.d[val] = self.d.get(val, 0) + 1
return val
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> res;
if(!root)
return res;
map<int, int> d;
get_sum(root, d);
int max_val = 0;
map<int, int>:: iterator it;
for(it = d.begin(); it != d.end(); it++){
if(it->second > max_val){
max_val = it->second;
res.erase(res.begin(), res.end());
res.push_back(it->first);
}else{
if(it->second == max_val)
res.push_back(it->first);
}
}
return res;
}
int get_sum(TreeNode* node, map<int, int>& d){
if(!node)
return 0;
int val = node->val + get_sum(node->left, d) + get_sum(node->right, d);
d[val]++;
return val;
}
};