closest-binary-search-tree-value

Strobogrammatic NumberClosest Binary Search Tree Value – LeetCode 270

Problem

Description

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Answer

Original

Code

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

思路

通过比较大小不断向下查找，记录下差值最小的值然后返回。时间复杂度$O(n)$，空间复杂度$O(1)$。

Better

思路

还没看到更好的思路。