Simple Python recursive solution (BFS) - O(n) 80ms

  • 0
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # @param {TreeNode} root
        # @return {integer}
        def minDepth(self, root):
            if not root:
                return 0
            nodes = collections.deque([(root, 1)])
            while nodes:
                node, curDepth = nodes.popleft()
                if node.left is None and node.right is None:
                    return curDepth
                if node.left:
                    nodes.append((node.left, curDepth + 1))
                if node.right:
                    nodes.append((node.right, curDepth + 1))

  • 1

    (Edit: This was about the old version using list instead of deque.)

    This is not O(n) but O(n^2), since every nodes.pop(0) takes linear time. If you have a complete tree, then popping the root shifts zero nodes, popping the next shifts one node, popping the next shifts two nodes, then three, then four, etc. You have a a quadratic amount of shifts.

  • 0

    Good catch. For future reference, one can simply change the [] to collections.deque() to get the real O(n) run time. (use double linked list array instead of a normal array)

Log in to reply

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