O(nlog(k)) time with O(k) heap space


  • 0
    S

    import heapq

    class Solution(object):

    def closestKValues(self, root, target, k):
        h = []
        heapq.heapify(h)
        self.helper(root, target, k, h)
        ret = []
        while len(h) > k:
            heapq.heappop(h)
        for i, j in h:
            ret.append(j)
        return ret
    
    def helper(self, root, target, k, h):
        if not root:
            return 
        heapq.heappush(h, (-abs(target-root.val), root.val))
        if len(h) > k:
            heapq.heappop(h)
        self.helper(root.left, target, k, h)
        self.helper(root.right, target, k, h)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.