```
def minDepth(self, root):
q = [(root,1)] if root else []
while q:
n, depth = q.pop(0)
if None == n.left == n.right:
return depth
if n.left: q.append((n.left, depth+1))
if n.right: q.append((n.right, depth+1))
return 0
```