Python Iterative Inorder: Using Heapq or Deque


  • 0
    L
    # Deque
    # 68 / 68 test cases passed.
    # Status: Accepted
    # Runtime: 62 ms  
    def closestKValues(self, root, target, k):
        deque = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if len(deque) < k:
                deque.append(root.val)
            else:
                if root.val <= target or abs(deque[0] - target) > abs(root.val - target):
                    deque.pop(0)
                    deque.append(root.val)                    
                else:
                    return deque
            root = root.right
        return deque
    
    # Heap
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        heapQ = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            heapq.heappush(heapQ, [abs(root.val-target), root.val])
            root = root.right
        return zip(*heapq.nsmallest(k, heapQ, key=lambda x:x[0]))[1]

Log in to reply
 

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