Two python solutions,but TLE using dfs


  • 0
    class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #iteratively
        if not root:return 0
        stack,res=[(root,1)],[]
        while stack:
            temp,nDepth=stack.pop()
            if not temp.left and not temp.right:
                res.append(nDepth)
            if temp.right:
                stack.append((root.right,nDepth+1))
            if temp.left:
                stack.append((root.left,nDepth+1))
        return min(res)
        #recursively
        '''import sys
        if not root:return 0
        if not root.left and not root.right:return 1
        if root.left:
            left=self.minDepth(root.left)
        else:
            left=sys.maxint
        if root.right:
            right=self.minDepth(root.right)
        else:
            right=sys.maxint
        return min(left,right)+1'''
    

    I have tried two solutions, but I couldn't pass it with dfs, I got TLE. Did someone solved the problem?


  • 0
    N

    I solved it using a traversal that compares the depth to the min depth once a leaf is reached.

    from sys import maxint
    class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            self.result = maxint
            self.inorder(root, 1)
            return self.result
    
        def is_leaf(self, node):
            return not (node.left or node.right)
    
        def inorder(self, node, depth):
            if not node:
                return depth -1
            elif self.is_leaf(node):
                self.result = min(self.result, depth)
                return depth
    
            self.inorder(node.left, depth + 1)
            self.inorder(node.right, depth + 1)
    

Log in to reply
 

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