[python3] 2476. Closest Nodes Queries in a Binary Search Tree

   한줄요약.   

이진트리가 주어져있다.

mini란 : quries[i] 보다 작거나 같은 수 중 가장 큰 숫자. 없으면 -1.

maxi란 : quries[i] 보다 크거나 같은 수 중 가장 작은 숫자. 없으면 -1.

각 qurey에 대한 mini와 maxi를 찾아서 반환해라 

 

원문 

You are given the root of a binary search tree and an array queries of size n consisting of positive integers.

Find a 2D array answer of size n where answer[i] = [mini, maxi]:

• mini is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead.
• maxi is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead.

Return the array answer.

 

example 1 

Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]

example2

Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]

 

   사용할 자료구조   

qurey의 각 원소의 mini, maxi를 찾기위해선, 대소비교가 필요하다.

접근이 편하도록 tree구조를 array구조로 바꾸고, 대소비교를 위해 크기순으로 sort시킨다. 

=> tree를 array로 변환하고, sort 시킨다. 

 

   예제에서 주어진 예외들   

1. qurey의 숫자를 tree에서 포함 할 경우 : mini, maxi 모두 qurey의 숫자와 같다. 

2. qurey의 숫자가 tree의 최댓값 보다 클 경우 ( 16  > 15 )  : mini는 tree의 최댓값, maxi는 -1,   => [15, -1] 

3. qurey의 숫자가 tree의 최솟값 보다 작을 경우 ( 3 < 4 )  :  mini는 -1, maxi는 tree의 최솟값 => [-1, 4] 

4. 기본case : [삽입할 index , index+1] 

*bisect_left/ bisect_right 사용시  배열내 삽입할 index를 반환한다. left, right 차이점은 배열내에 이미 삽입하려는 값이 있을경우 오른쪽에 삽입할 건지, 왼쪽에 삽입할 것인지의 차이이다. 

 

  코드.  

 

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from bisect import bisect_right, bisect_left



class Solution:
    #전위 순회 //루트-왼-오
    def __init__(self):
        self.a=[]
    
    def pre_order(self, node):
        #print(node.val, end='') '
        self.a.append(node.val)
        if node.left != None:
            self.pre_order(node.left)
        if node.right != None:
            self.pre_order(node.right)
            
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        self.pre_order(root)
        self.a.sort()
        ret=[]
        for v in queries:
            i = bisect_left(self.a, v)
            #print("index:", i)
            
            if i >=len(self.a):
                ret.append([self.a[-1],-1])            
            elif v == self.a[i]:
                ret.append([v,v])
            elif i == 0:
                ret.append([-1, self.a[0]])
            else : 
                ret.append([self.a[i-1],self.a[i]])
            
                 
        
        return ret