LC272. Closest Binary Search Tree Value II

# 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

# time O(NlgK)  space O(H+K)
from heapq import heappush, heappop
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        """
        1. inorder traversal to return sorted list // or insert (distance, current node ) into heap 
        2. sort by  num-taret  (distance with target) // or keep size k of heap 
        3. get first k items // or return list of node value 
        """
        hp = []
        def inor(node):
            if not node:
                return 
            inor(node.left)
            heappush(hp,(-abs(node.val-target),node.val))
            if len(hp)> k:
                heappop(hp)
            
            inor(node.right)
            
        inor(root)
        return [v for _, v in hp]