C++ BST O(nlogk) 84.64%


  • 4
    F

    Or just use std::set, implementing BST in C++ is a pain in ass.

    /**
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode* left;
     *     TreeNode* right;
     * 
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = nullptr;
     *         this->right = nullptr;
     *     }
     * };
     */
    class BST {
    public:
        TreeNode* root;
        
        BST() {
            root = nullptr;
        }
        
        TreeNode* insert(int val) {
            root = insert(root, val);
            return root;
        }
        
        TreeNode* insert(TreeNode* now, int val) {
            if (!now) now = new TreeNode(val);
            else if (val > now->val) now->right = insert(now->right, val);
            else if (val < now->val) now->left = insert(now->left, val);
            return now;
        }
        
        TreeNode* remove(int val) {
            root = remove(root, val);
            return root;
        }
        
        TreeNode* remove(TreeNode* now, int val) {
            if (!now) {
                return nullptr;
            } else if (val < now->val) {
                now->left = remove(now->left, val);
            } else if (val > now->val) {
                now->right = remove(now->right, val);
            } else {
                if (!now->left) {
                    TreeNode *tmp = now->right;
                    delete now;
                    return tmp;
                } else if (!now->right) {
                    TreeNode *tmp = now->left;
                    delete now;
                    return tmp;
                } else {
                    TreeNode *tmp = now->right;
                    while (tmp->left) tmp = tmp->left;
                    now->val = tmp->val;
                    now->right = remove(now->right, now->val);
                }
            }
            return now;
        }
        
        bool search(int val, int t) {
            return search(root, val, t);
        }
        
        bool search(TreeNode* now, long val, int t) {
            if (!now) return false;
            else if (abs(val - now->val) <= t) return true;
            else if (now->val - t > val) return search(now->left, val, t);
            else return search(now->right, val, t);
        }
    };
    
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (nums.empty() || k == 0) return false;
            BST bst;
            for (int i = 1; i < nums.size(); ++i) {
                bst.insert(nums[i - 1]);
                if (i > k) bst.remove(nums[i - k - 1]);
                if (bst.search(long(nums[i]), t)) return true;
            }
            return false;
        }
    };
    

  • 1
    B

    the most understandable solution for me


Log in to reply
 

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