Leetcode - 270. Closest Binary Search Tree Value

문제

주어진 target값이 트리 노드중에 어떤값과 가장 가까운지 찾아라.

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

해결

해당 값을 binary search하여 찾음. (해설 답안은 더 간결한데 확인해볼것 https://leetcode.com/problems/closest-binary-search-tree-value/solution/)

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int left_most = -1;
        int right_lest = -1;
        TreeNode *node = root;
        while (node) {
            if (target < (double)node->val) {
                right_lest = node->val;
                node = node->left;
            } else if ((double)node->val < target) {
                left_most = node->val;
                node = node->right;
            } else { // node->val == target
                return node->val;
            }
        }            
        if (left_most == -1 && right_lest != -1)
            return right_lest;
        else if (left_most != -1 && right_lest == -1)
            return left_most;
        // left_most   target  right_lest
        double a = right_lest - (double)target;
        double b = (double)target - left_most;
        return a > b ? left_most : right_lest;
    }
};