O(n) time O(1) space Python solution using Morris traversal


  • 1
    C
    import collections
    def closestKValues(root, target, k):
        ret = collections.deque()
        
        while root:
            if root.left:
                temp = root.left
                while temp.right and temp.right != root:
                    temp = temp.right
                if temp.right:
                    temp.right = None
                else:
                    temp.right = root
                    root = root.left
                    continue
                
            diff = abs(root.val - target)
            if len(ret) < k:
                ret.append((root.val, diff))
            elif ret[0][1] > diff:
                ret.popleft()
                ret.append((root.val, diff))
            else:
                break
    
            root = root.right
            
        return map(lambda x: x[0], ret)

Log in to reply
 

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