C++ O(N) solution with an inorder traversal (100 percentile)


  • 0
    G
    class Solution {
    public:
    
        unordered_map<int,int> Freq;
        
        bool Inorder(TreeNode *root,int &Sum,int &Max)
        {
            if(root == NULL)
            {
                return false;
            }
            
            if(root->left == NULL && root->right == NULL)
            {
                Freq[root->val]++;
                Sum += root->val;
                Max = max(Max,Freq[root->val]);
                return true;
            }
            
            int Sum1 = 0, Sum2 = 0;
            bool b1 = Inorder(root->left,Sum1,Max);
            bool b2 = Inorder(root->right,Sum2,Max);
            
            if(b1)
            {
                Sum += Sum1;
            }
            
            if(b2)
            {
                Sum += Sum2;
            }
            
            Sum+= root->val;
            Freq[Sum]++;
            Max = max(Max,Freq[Sum]);
            return (true);
        }
    
    
        vector<int> findFrequentTreeSum(TreeNode* root) 
        {
            int Sum = 0;
            int Max = 0;
            Inorder(root,Sum,Max);
            
            vector<int> Res;
            
            for(auto &f : Freq)
            {
                if(f.second == Max)
                {
                    Res.push_back(f.first);
                }
            }
            
            return (Res);
        }
    };

Log in to reply
 

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