給出二叉樹的根,找出出現次數最多的子樹元素和。一個結點的子樹元素和定義為以該結點為根的二叉樹上所有結點的元素之和(包括結點本身)。然后求出出現次數最多的子樹元素和。如果有多個元素出現的次數相同,返回所有出現次數最多的元素(不限順序)。
?
示例 1
輸入:
5/ \ 2 -3
返回?[2, -3, 4],所有的值均只出現一次,以任意順序返回所有值。
示例?2
輸入:
5/ \ 2 -5
返回?[2],只有 2 出現兩次,-5 只出現 1 次。
class Solution {
public:vector<int> findFrequentTreeSum(TreeNode* root) {vector<int> res;unordered_map<int, int> m;int cnt = 0;postorder(root, m, cnt, res);return res;}int postorder(TreeNode* node, unordered_map<int, int>& m, int& cnt, vector<int>& res) {if (!node) return 0;int left = postorder(node->left, m, cnt, res);int right = postorder(node->right, m, cnt, res);int sum = left + right + node->val;++m[sum];if (m[sum] >= cnt) {if (m[sum] > cnt) res.clear();res.push_back(sum);cnt = m[sum];}return sum;}
};
?