C++ 6ms solution - finding predecessor && successor of target


  • 0
    B

    The idea is finding the predecessor and succesor of the target value in the BST.
    Similar to the problem Inorder Successor of BST
    If target is found, the closest among both is returned.
    Else if one of them is found and other is null, return that one
    else if none exist, return the target itself.

    int closestValue(TreeNode* root, double target) {
            
            if (!root)
                return 0;
            
            TreeNode* pred = findPred(root, target);
            TreeNode* succ = findSucc(root, target);
            
            if (pred && succ) {
                if (abs(pred->val - target) < abs(succ->val - target))
                    return pred->val;
                else
                    return succ->val;
            } else if (!pred && succ)
                return succ->val;
            else if (pred && !succ)
                return pred->val;
            else 
                return root->val;
        }
        
        TreeNode* findPred(TreeNode* root, double target) {       
            TreeNode* res = nullptr;
            
            while (root) {            
                if (root->val > target)
                    root= root->left;
                else {
                    res = root;
                    root = root->right;
                }            
            }
            
            return res;
        }
        
        TreeNode* findSucc(TreeNode* root, double target) {
            TreeNode* res = nullptr;
            
            while(root) {
                if (root->val < target)
                    root = root->right;
                else {
                    res = root;
                    root = root->left;
                }
            }
            return res;
        }
    

    The code is verbose, but easy to understand.


Log in to reply
 

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