深度优先算法解决二叉树的最大、最小深度问题

对于深度优先搜索算法中经常会遇到的一个经典问题，关于求二叉树的最大、最小深度问题。

对于二叉树的最大深度和最小深度的求解，首先要知道这两个深度的定义，对于最大深度就是指二叉树的根节点与最远的叶子节点之间的高度，最小深度相对的就是指根节点与最近的叶子节点之间的高度，对于以下给定的二叉树，分别看最大深度和最小深度。

添加图片注释，不超过 140 字（可选）

对于上面的这个给定的二叉树的最大深度就是从根节点1到叶节点5之间的高度，也即是最大深度为3，而最小深度就是根节点1到叶节点2之间的高度，也即是最小深度为2。

添加图片注释，不超过 140 字（可选）

对于上面的这个给定的二叉树的最大深度和最小深度都是根节点1到叶节点3之间的高度，也即是最大深度最小深度都是3。

对于二叉树的深度求解，可以将这个问题不断拆分为求子树深度的问题，也即是对子树深度求解作为原问题的子问题，先解决子问题，从而得到原问题的解。整个过程是通过递归调用的方式，当遇到的节点为空时，就将0传递给上层，这也就有了递归的终止条件，而当遇到的节点不为空时，将该节点为根节点的子树的深度值返回给上层节点，逐渐传递直到二叉树的根节点，这也就最终得到返回的给定二叉树的最大深度。整个过程中先计算的深度的都是叶子节点，因为叶子节点没有子节点，所以递归到最后遇到的节点就是为空，逐层返回，最终也就返回到了根节点。

使用python求解最大深度的代码如下：

def maxDepth(root):
    if root:
        return 0
    else:
        return max(maxDepth(root.left),maxDepth(root.right))+1

对于最小深度问题，主要是需要注意一个问题，那就是如果说给定的二叉树只有左子树或者只有右子树，我们在求最小深度的过程中不能忽略没有子树的一侧，所以当给定二叉树只有左子树的时候，右侧的空子树就不应该返回给上层，只需要将左子树的求出的深度加一返回给根节点即可；同理的，当只有右子树的时候，左子树也不应该返回给上层，把右子树求出的深度加一返回给根节点。而对于有左右子树的二叉树，可以直接使用最大深度的返回方式来求解，这样就将所有情况都考虑到了。

添加图片注释，不超过 140 字（可选）

如下是最小深度的python代码实现：

def minDepth(root):
    if not root:
        return 0
    if not root.left:
        return self.minDepth(root.right)+1
    elif not root.right:
        return self.minDepth(root.left)+1
    else:
        return min(minDepth(root.left),minDepth(root.right))+1