Concise Python solution using generators


  • 0
    X

    The idea is define two generators to get the predecessor and successor.

    
    class Solution(object):
        def closestKValues(self, root, target, k):
            pre, suc = self.getPreOrSuc(root,target,1),self.getPreOrSuc(root,target,0)
            res = []
            p, s = next(pre,float('-inf')), next(suc,float('inf'))
            while len(res) < k:
                if abs(p-target) < abs(s-target):
                    res.append(p)
                    p = next(pre,float('inf'))
                else:
                    res.append(s)
                    s = next(suc,float('inf'))
            return res
            
        def getPreOrSuc(self,root,target,pre):
            if root:
                for n in self.getPreOrSuc(root.right if pre else root.left,target,pre):
                    yield n
                if (root.val <= target and pre) or (root.val > target and not pre):
                    yield root.val
                for n in self.getPreOrSuc(root.left if pre else root.right,target,pre):
                    yield n

  • 0
    X

    Not sure if this is faster or not, as leetcode is not showing the graph.


Log in to reply
 

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