O(nlogn) python heap(priority queue) solution


  • 0
    S

    No fancy code. Idea is simple, inorder traversal and push compare value in heap. Then pop the first k values.

    class Solution(object):
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        values = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                heapq.heappush(values, (abs(root.val - target), root.val))
                root = root.right
        return [heapq.heappop(values)[1] for _ in range(k)]

Log in to reply
 

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