C++ Solution using postorder traversal


  • 0
    A

    Use a postorder traversal algorithm. Keep two maps during the traversal:
    treeSum map (TreeNode *, int) stores the tree sum under each node.
    treeSumCount map (int, int) stores the occurrences of each sum.

    class Solution {
    public:
        vector<int> findFrequentTreeSum(TreeNode* root) {
            vector<int> result;
            if (!root) {
                return result;
            }
            unordered_map<int, int> treeSumCount;
            unordered_map<TreeNode *, int> treeSum;
            int maxCount = 0;
            findFrequentTreeSumHelper(root, treeSum, treeSumCount, maxCount);
            for (auto it = treeSumCount.begin(); it != treeSumCount.end(); ++it) {
                if (it->second == maxCount) {
                    result.push_back(it->first);
                }
            }
            return result;
        }
        
        void findFrequentTreeSumHelper(TreeNode *root, unordered_map<TreeNode *, int> &treeSum, 
                                       unordered_map<int, int> &treeSumCount, int &maxCount) {
            int sum = 0;
            if (root->left) {
                findFrequentTreeSumHelper(root->left, treeSum, treeSumCount, maxCount);
                sum += treeSum[root->left];
            }
            
            if (root->right) {
                findFrequentTreeSumHelper(root->right, treeSum, treeSumCount, maxCount);
                sum += treeSum[root->right];
            }
            
            sum += root->val;
            treeSum[root] = sum;
            if (++treeSumCount[sum] > maxCount) {
                maxCount = treeSumCount[sum];
            }
        }
    };
    

Log in to reply
 

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