19ms, PostOderTraversal, hash, rehash, in C++

  • 0

    use hash: key is subtree's sum. value is the sum's frequency
    use rehash: key is the sum's frequency, value is the vector of the subtrees' sum which is with that frequency

    class Solution {
        vector<int> findFrequentTreeSum(TreeNode* root) {
            if(root == NULL) return {};
            unordered_map<int, int> hash;
            map<int, vector<int>> rehash;
            vector<int> res;
            Sum(root, hash, rehash);
            return rehash.rbegin() -> second;
        int Sum(TreeNode* root, unordered_map<int, int> & hash, map<int, vector<int>> & rehash){
            if(root == NULL) return 0;
            int left = Sum(root -> left, hash, rehash);
            int right = Sum(root -> right, hash, rehash);
            int sum = left + right + root -> val;
            if(rehash.find(hash[sum]) == rehash.end()) rehash[hash[sum]] = {sum};
            else rehash[hash[sum]].push_back(sum);
            return sum;

Log in to reply

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