My simple C++ solution using unordered_map


  • 0
    T
    #include <vector>
    #include <unordered_map>
    #include <utility>
    #include <algorithm>
    #include <iostream>
    
    using std::vector;
    using std::unordered_map;
    using std::pair;
    
    /**
     * 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) {
        if (root == nullptr) return{};
        unordered_map<int, int> dict;
        calculate(root, dict);
    
        std::vector<std::pair<int, int>> vec{ dict.begin(), dict.end() };
        std::sort(vec.begin(), vec.end(), [](const std::pair<int, int>& left, const std::pair<int, int>& right) {
          return left.second > right.second;
        });
    
        std::vector<int> result{ vec.begin()->first };
        for (auto itr = vec.begin() + 1; itr != vec.end(); ++itr) {
          if ((*itr).second != vec.begin()->second)
            break;
    
          result.push_back((*itr).first);
        }
    
        return result;
      }
    
    private:
      int calculate(TreeNode* root, unordered_map<int, int> &dict) {
        if (root == nullptr)
          return 0;
    
        if (!root->left && !root->right) {
          ++dict[root->val];
          return root->val;
        }
    
        int left_sum = calculate(root->left, dict);
        int right_sum = calculate(root->right, dict);
        
        int sum = left_sum + right_sum + root->val;
        ++dict[sum];
    
        return sum;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.