Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

递归（dfs）:

递归解法急速判断左右两边子树哪个depth最小，要注意如果有个节点只有一边孩子时，不能返回0，要返回另外一半边的depth。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        if left and right:
            return min(left, right) + 1
        return max(left, right) + 1

BFS：

用bfs的queue储存每层的element，当第一次发现没有left和right的element，return层数。

一定要用（root，层数），与path sum相似。防止累计。

注意：在while loop里要判断node！＝none，如果node＝none，none object没有left和right

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        queue = [(root,1)]
        while queue:
            node, level = queue.pop(0)
            if not node:
                continue
            if not node.left and not node.right:
                return level

            queue.append((node.left,level+1))
            queue.append((node.right, level+1))