C++ BST Solution


  • 0
    J
    struct TNode {
        TNode(int val) : val(val), cnt(0), left(NULL), right(NULL) {}
    
        int val;
        int cnt;
        TNode* left;
        TNode* right;
    };
    
    class Solution {
    public:
    int insertNode(TNode* curNode, int val, int t) {
        if(curNode->val < val) {
            if(curNode->right) 
                return insertNode(curNode->right, val, curNode->cnt + t + 1);
    
            TNode* newNode = new TNode(val);
            curNode->right = newNode;
            t += curNode->cnt + 1;
        }
        else if(val <= curNode->val) {
            curNode->cnt++;
            if(curNode->left) 
                return insertNode(curNode->left, val, t);
            
            TNode* newNode = new TNode(val);
            curNode->left = newNode;
        }
    
        return t;
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.size() == 0) return vector<int>();
        
        vector<int> result = { 0 };
        TNode *root = new TNode(nums.back());
        for(int i = nums.size() - 2; i >= 0; i--) 
            result.push_back(insertNode(root, nums[i], 0));
    
        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.