Find Closest Value in BST

리컬시브를 사용하기 위해 헬퍼 함수가 필요할것이고, 결과값이 타겟값과 가장 가까운 값이고 리턴 값이므로 헬퍼함수의 파라미터에 넣어줘야 값이 바뀔때마다 업데이트 할것이다.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None 
        self.right = None 

def getClosest(curr, target, closestValue):
    if not curr:
        return closestValue
    if abs(curr.value - target) < abs(closestValue - target):
        closestValue = curr.value
    if curr.value == target:
        return closestValue
    if curr.value > target:
        closestValue = getClosest(curr.left, target, closestValue)
    else:
        closestValue = getClosest(curr.right, target, closestValue)
    return closestValue

def findClosestValueInBst(tree, target):
    if tree.value == target:
        return tree.value
    return getClosest(tree, target, float("inf"))

    
# This is the class of the input tree. Do not edit.
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

현재값과 타겟값의 차이와 가장 가까운값과 타겟값의 차이를 비교하여 현재값과 타겟값이 더 작다면 가까운값을 현재값으로 업데이트 해준다. 값이 같다면 가장 가까운값이니, 그 값을 바로 리턴하면 된다.

현재값보다 타겟값이 크다면 오르쪽으로 반대라면 왼쪽으로 이동하면서 트리를 아래로 탐색한다. 리턴값은 당연히 가장 가까운값.