Recursive O(logn) solution.


  • 0
    Z
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int ret_;
        int closestValue(TreeNode* root, double target) {
            if (root == nullptr) {
                return 0;
            }
            ret_ = root->val;
            return helper(root, target, abs(target - root->val));
        }
        
        int helper(TreeNode *root, double target, double dis) {
            if (root == nullptr) {
                return ret_;
            }
            const double new_dis = abs(target - root->val);
            if (new_dis < dis) {
                ret_ = root->val;
            }
            dis = min(new_dis, dis);
            if (target < root->val) {
                return helper(root->left, target, dis);
            } else {
                return helper(root->right, target, dis);
            }
        }
    };
    

Log in to reply
 

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