python dfs and bfs solutions


  • 0
    H
    # dfs traversal
    class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.min = 1e9
            def helper(root, depth):
                if not root:
                    return
                if not root.left and not root.right:  # check whether or not is a leaf
                    self.min = min(depth, self.min)
                    return
                helper(root.left, depth + 1)
                helper(root.right, depth + 1)
    
            if not root:
                return 0
            helper(root, 1)
            return self.min
    
    # bfs solutions
    class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            queue = [root]
            depth = 0
            while queue:
                depth += 1
                size = len(queue)
                for i in range(size):
                    top = queue.pop(0)
                    if not top:
                        continue
                    if not top.left and not top.right:
                        return depth
                    queue.append(top.left)
                    queue.append(top.right)
    
            return depth
    

  • 0

    The time complexity of your pop(0) is O(n), use collections deque and deque.popleft() is better.


Log in to reply
 

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