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 else: return min(self.minDepth(root.left),self.minDepth(root.right))+1
Not sure if faster, but less lines and same idea: https://oj.leetcode.com/discuss/11112/my-solution-in-python
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)
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])
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.