My Python Solution: How Can it be Faster?

  • 1

    This is my Python solution to the minimum depth of binary tree problem. The solution takes slightly more than 250ms and apparently is not the best solution. I wonder how it can be faster:

    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # @param root, a tree node
        # @return an integer
        def minDepth(self, root):
            if root is None:
                return 0
            elif root.left is None and root.right is None:
                return 1
            elif root.left is None:
                return self.minDepth(root.right)+1
            elif root.right is None:
                return self.minDepth(root.left)+1
                return min(self.minDepth(root.left),self.minDepth(root.right))+1

  • 1

    Not sure if faster, but less lines and same idea:

  • 0
      elif root.left is None and root.right is None:
            return 1

    The 2 lines above is redundant since it's subset of set( root.left is None) Or (root.right is None)

  • 0

    My iterative solution on BSF beat 99% of submissions, but I feel it could be even faster if I had an actual queue implementation instead of using a list.

    class Solution(object):
        def minDepth(self, root):
            if not root:
                return 0
            queue = [[root,1]]
            while True:
                node, depth = queue.pop(0)
                if not (node.left or node.right):
                    return depth
                if node.left:
                    queue.append([node.left, depth+1])
                if node.right:
                    queue.append([node.right, depth+1])

Log in to reply

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