企业网站备案收费,长沙网站建设市场低价,网站关键词快速优化,asp网站空间申请1. 题目
给你一个二叉树的根结点#xff0c;请你找出出现次数最多的子树元素和。 一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和#xff08;包括结点本身#xff09;。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同请你找出出现次数最多的子树元素和。 一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和包括结点本身。
你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同返回所有出现次数最多的子树元素和不限顺序。
示例 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_mapint,int m;vectorint ans;int maxCount 0;int s;
public:vectorint 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 lrroot-val;if(m[s] maxCount)maxCount m[s];return s;}
};32 ms 23 MB
