C++_9ms_iterative method_with brief explanation


  • 0

    For the target, if it is less than root->val, we move our root to root->left, else we will move our root to root->right. Then each time we will compare the difference: abs(root->val - target) with our local minimized difference diff, and update the information.

    The reason why we should update the root by comparing it with the target is that the BST is increasing in in-order traverse, so we can find out the closest value of our target in one side of the root.

    class Solution {
    public:
    int closestValue(TreeNode* root, double target) {
        int res = root->val;
        double diff = abs(root->val * 1.0 - target);
    
        while(root != nullptr){
            double d = abs(root->val * 1.0 - target);
            if(diff > d){
                res = root->val;
                diff = d;
            }
            if(target < root->val){root = root->left;}
            else{root = root->right;}
        }
        return res;
    }
    };

Log in to reply
 

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