# Simple DFS + Priority Queue Python Solution

• ``````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``````

• Cool, but this takes `O(NlogN)` time. You can do it in `O(k + (N - k)*log(k))`. Check out https://leetcode.com/discuss/110964/python-solution-o-n-klog-k-time

• why this is O(nlogn)? i think it is O(n), or you can say O(kn)

• @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?

• @agave
thinks for your instruction.

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