[LeetCode]508. Most Frequent Subtree Sum

题目描述

思路

递归，保存每次的和到map中，同时计算和最多出现的次数 思路简单，回顾树的操作

代码

#include <iostream> #include <vector> #include <unordered_map> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; int countSubtreeSums(TreeNode *r, unordered_map<int, int> &countSum, int& max){ if (!r) return 0; int sum = r->val; sum += countSubtreeSums(r->left, countSum, max); sum += countSubtreeSums(r->right, countSum, max); ++countSum[sum]; if (countSum[sum] > max) max = countSum[sum]; return sum; } vector<int> findFrequentTreeSum(TreeNode* root) { unordered_map<int, int> countSum; int max = 0; countSubtreeSums(root, countSum, max); vector<int> res; for (const auto &x : countSum){ if (max == x.second) res.push_back(x.first); } return res; } int main(){ int depth = 4; TreeNode *root = new TreeNode(5); TreeNode *left = new TreeNode(2); TreeNode *right = new TreeNode(-3); root->left = left; root->right = right; vector<int> res = findFrequentTreeSum(root); for (auto &p : res){ cout << p << endl; } system("pause"); }