class Solution(object):
def closestKValues(self, root, target, k):
"""
:type root: TreeNode
:type target: float
:type k: int
:rtype: List[int]
"""
def dfs(root, target, heap):
if root is None:
return
dfs(root.left, target, heap)
heapq.heappush(heap, (abs(root.val  target), root.val))
dfs(root.right, target, heap)
heap = []
dfs(root, target, heap)
output = []
for _ in range(k):
output.append(heapq.heappop(heap)[1])
return output
Simple DFS + Priority Queue Python Solution


Cool, but this takes
O(NlogN)
time. You can do it inO(k + (N  k)*log(k))
. Check out https://leetcode.com/discuss/110964/pythonsolutiononklogktime

@weiheng4 think more carefully. You are using a heap. Each op takes O(log x) where x is the size. What is the max size of that heap? How many time you perform extraction if k == n?
