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


  • 0
    S
    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
            
    

Log in to reply
 

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