4ms C recursive solution


  • 0
    L

    The key point is to select the node which has difference between root and its children.

    struct TreeNode *get_closest_node(struct TreeNode *root, double target) {
        
        while (root) {
            double diff_root = fabs(target - root->val);
            if (root->val > target) {
                if (!root->left)
                    return root;
                double diff_left = target - root->left->val;
                if (diff_left < 0) {
                    root = root->left;
                } else {
                    if (!root->left->right) {
                        return diff_left < diff_root ? root->left : root;
                    } else {
                        struct TreeNode *node = get_closest_node(root->left, target);
                        diff_left = fabs(target - node->val);
                        return diff_left < diff_root ? node : root;
                    }
                }
            } else {
                if (!root->right)
                    return root;
                double diff_right = target - root->right->val;
                if (diff_right > 0) {
                    root = root->right;
                } else {
                    if (!root->right->left) {
                        diff_right = fabs(diff_right);
                        printf("diff_right=%f, diff_root=%f\n", diff_right, diff_root);
                        return diff_right < diff_root ? root->right : root;
                    } else {
                        struct TreeNode *node = get_closest_node(root->right, target);
                        diff_right = fabs(target - node->val);
                        return diff_right < diff_root ? node : root;
                    }
                }
            }
        }
    }
    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    int closestValue(struct TreeNode* root, double target) {
        if (root == NULL)
            return -1;
            
        return get_closest_node(root, target)->val;
    }

Log in to reply
 

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