class Solution:

# @param {TreeNode} root

# @return {integer}

def minDepth(self, root):

if root is None:

return 0

if root.left is None and root.right is None:

return 1

else:

leftDepth = 1 + self.minDepth(root.left)

rightDepth = 1 + self.minDepth(root.right)

if leftDepth == 1:

return rightDepth

elif rightDepth == 1:

return leftDepth

else:

return min(leftDepth,rightDepth)