Sharing my 36ms C++solution


  • 0
    T
    // definition of BST, specifically for this problem
    struct myTreeNode
    {
        int val; // the value
        int nLess; // the number of nodes whose value is less than the value of this node
        int nSame; // the number of nodes whose value is the same as that of this node
        myTreeNode* left;
        myTreeNode* right;
        myTreeNode(int value)
        {
            val = value;
            nLess = 0;
            nSame = 1;
            left=NULL;
            right=NULL;
        }
    };
    
    void insert(myTreeNode* root, int value, int& nSmaller)
    {
        if(value<root->val)
        {
            root->nLess++;
            if(root->left==NULL)
                root->left = new myTreeNode(value);
            else
                insert(root->left, value, nSmaller);
        }
        else if(value>root->val)
        {
            nSmaller += (root->nSame+root->nLess);
            if(root->right==NULL)
                root->right = new myTreeNode(value);
            else
                insert(root->right, value, nSmaller);
        }
        else
        {
            root->nSame++;
            nSmaller += root->nLess;
        }
    }
    
    class Solution {
    public: 
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> result;
            result.resize(n);
            
            if(n==0)
                return result;
            
            result[n-1] = 0;
            myTreeNode* root = new myTreeNode(nums[n-1]);
            
            int nLess;
            for(int i=n-2; i>=0; i--)
            {
                nLess = 0;
                insert(root, nums[i], nLess);
                result[i] = nLess;
            }
            
            return result;
        }
    };

Log in to reply
 

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