题目描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：
叶子节点是指没有子节点的节点
示例：
给定二叉树 [3,9,20,null,null,15,7]， 返回它的最小深度2。
image.png
解题思路一：递归
这里要注意两点：
- 叶子节点是指没有子节点的节点
- 最小深度是从根节点到最近叶子节点的最短路径上的节点数量
例如：二叉树[1,2]，返回的最小深度为2，并非1。（即需要排除None子节点）
image.png
# 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
left = self.minDepth(root.left)
right = self.minDepth(root.right)
if left and right:
return min(left, right) + 1 # 当双子节点不为None时，返回其最小深度
else:
return max(left, right) + 1 # 当其中一个子节点为None时，返回其最大深度
———————————————————————————————————————
解题思路二：深度优先搜索迭代
我们可以利用栈将上述解法中的递归变成迭代。
想法是对于每个节点，按照深度优先搜索的策略访问，同时在访问到叶子节点时更新最小深度。
我们从一个包含根节点的栈开始，当前深度为 1 。
然后开始迭代：弹出当前栈顶元素，将它的孩子节点压入栈中。当遇到叶子节点时更新最小深度。
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
stack, min_depth = [(1, root),], float('inf')
while stack:
depth, root = stack.pop()
children = [root.left, root.right]
if not any(children):
min_depth = min(depth, min_depth)
for c in children:
if c:
stack.append((depth + 1, c))
return min_depth
复杂度分析
- 时间复杂度：每个节点恰好被访问一遍，复杂度为 O(N)。
- 空间复杂度：最坏情况下我们会在栈中保存整棵树，此时空间复杂度为 O(N)。
解题思路三：宽度优先搜索迭代
深度优先搜索方法的缺陷是所有节点都必须访问到，以保证能够找到最小深度。因此复杂度是 O(N)。
一个优化的方法是利用宽度优先搜索，我们按照树的层次去迭代，第一个访问到的叶子就是最小深度的节点，这样就不要遍历所有的节点了。
from collections import deque
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
node_deque = deque([(1, root),])
while node_deque:
depth, root = node_deque.popleft()
children = [root.left, root.right]
if not any(children):
return depth
for c in children:
if c:
node_deque.append((depth + 1, c))
复杂度分析
- 时间复杂度：最坏情况下，这是一棵平衡树，我们需要按照树的层次一层一层的访问完所有节点，除去最后一层的节点。这样访问了 N/2 个节点，因此复杂度是 O(N)。
- 空间复杂度：和时间复杂度相同，也是 O(N)。
