Python Inorder Traversal Solution O(n)


  • 1
    V
    def closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        inorder=self.inorder_traversal(root)
        result=inorder[:k]
        for i in xrange(k,len(inorder)):
            if abs(result[0]-target)>abs(inorder[i]-target):
                result.append(inorder[i])
                result=result[1:]
            else:
                return result
        return result
    
    
    def inorder_traversal(self,root):
        stack=[]
        res=[]
        #stack.append(root)
        while stack or root:
            if root:
                stack.append(root)
                root=root.left
            else:
                root=stack.pop()
                res.append(root.val)
                root=root.right
        return res

Log in to reply
 

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