straightforward O(klogN) solution with comment


  • 0

    It uses two functions findPre() and findSuc() to get predecessor and successor node values given a target value. Then It obtains the closest value and gets the next closest value one by one.

      def closestKValues(self, root, target, k):
    
        def findPre(cur, val, res):
          if not cur: return
          if cur.val == val:
            # the maximum value in left subtree is predecessor
            if cur.left:
              tmp = cur.left
              while(tmp.right):
                tmp = tmp.right
              res.append(tmp)
            return
          if cur.val > val:
            findPre(cur.left, val, res)
          else:
            res.append(cur)
            findPre(cur.right, val, res)
    
        def findSuc(cur, val, res):
          if not cur: return
          if cur.val == val:
            # the minimum value in right subtree is successor
            if cur.right:
              tmp = cur.right
              while(tmp.left):
                tmp = tmp.left
              res.append(tmp)
            return
          if cur.val > val:
            res.append(cur)
            findSuc(cur.left, val, res)
          else:
            findSuc(cur.right, val, res)
    
        if k == 0: return []
        # find node value closet to target
        cur = root
        min_diff, closest = float("inf"), None
        while cur:
          if abs(cur.val - target) < min_diff:
            min_diff = abs(cur.val - target)
            closest = cur.val
          if cur.val > target:
            cur = cur.left
          elif cur.val < target:
            cur = cur.right
          else:
            closest = cur.val
            break
        # collect closest values from middle to the sides (left & right)
        res = deque([closest])
        while k > 1:
          pre, suc = [], []
          findPre(root, res[0], pre)
          findSuc(root, res[-1], suc)
    
          if not pre:
            res.append(suc[-1].val)
          elif not suc:
            res.appendleft(pre[-1].val)
          else:
            if abs(pre[-1].val - target) < abs(suc[-1].val - target):
              res.appendleft(pre[-1].val)
            else:
              res.append(suc[-1].val)
          k -= 1
        return list(res)
    

Log in to reply
 

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