BST based C++


  • 0
    F
    struct Node
    {
        int val,  count = 1;
        Node * left = nullptr, * right = nullptr;
        Node (int _val) : val(_val) {}
        ~Node() {
            delete left;
            delete right;
        }
    };
    class BST
    {
        Node * root = nullptr;
    public:
        int insert(int num, Node *& cur)
        {
            if (cur == nullptr)
                return cur = new Node(num), 0;
            cur->count ++;
            if (num <= cur->val)
                return insert(num, cur->left);
            else
                return insert(num, cur->right) + (cur->left == nullptr ? 1 : cur->left->count + 1);
        }
        int insert(int num)
        {
            return insert(num, root);
        }
        virtual ~BST()
        {
            delete root;
        }
    };
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> result;
            BST bst;
            for (int i = nums.size() - 1; i >= 0; --i)
                result.push_back(bst.insert(nums[i]));
            reverse(result.begin(), result.end());
            return result;
        }
    };
    

Log in to reply
 

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