# O(1) space, O(klogn) time python solution

• ``````class Solution(object):
def closestKValues(self, root, target, k):
"""
:type root: TreeNode
:type target: float
:type k: int
:rtype: List[int]
"""
#first find the closet value, then find the predecessor or successor of the node, merge k
closet = root
cur = root
while cur:
if abs(cur.val - target) < abs(target - closet.val):
closet = cur
if cur.val > target:
cur = cur.left
else:
cur = cur.right
pre = self.getPredecessor(root, closet)
succ = self.getSuccessor(root, closet)
res = [closet.val]
k -= 1
while k and pre and succ:
if abs(pre.val - target) < abs(succ.val - target):
res.append(pre.val)
pre = self.getPredecessor(root, pre)
else:
res.append(succ.val)
succ = self.getSuccessor(root, succ)
k -= 1

if k > 0:
if pre:
while k:
res.append(pre.val)
pre = self.getPredecessor(root, pre)
k -= 1
else:
while k:
res.append(succ.val)
succ = self.getSuccessor(root, succ)
k -= 1
return res

def getPredecessor(self, root, p):
pre = None
while root:
if root.val < p.val:
pre = root
root = root.right
else:
root = root.left
return pre

def getSuccessor(self, root, p):
succ = None
while root:
if root.val > p.val:
succ = root
root = root.left
else:
root = root.right
return succ

``````

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