题目要求
给定一个二叉树，求其最小深度。
最大深度：从根结点到叶子结点包含的节点的最小个数。
注意: 叶子结点说的是一个没有孩子的节点。
注意和 解答：leetcode 104. Maximum Depth of Binary Tree （求二叉树的最大深度,DFS,BFS）的不同！！！！！！！！
输入示例
Example:输入一个二叉树 [3,9,20,null,null,15,7],3/ \9 20/ \15 7
return its depth = 2.
解题思路
相比求二叉树的最大深度，本题还是有一定的难点，首先我们不能像求最大深度那样直接递归的写出如下的代码（只把max改成min是有问题的）
class Solution {
public:int minDepth(TreeNode* root) {
if(root == NULL) return 0;return min(1+minDepth(root->left), 1+minDepth(root->right));}
};
举个例子来看，当树只有两个节点的时候,我们按照上面的代码结果将是：1。而正确答案应该是2。看出问题所在了吗？ 实际上并不是我们的代码写错了，而是我们忽略了向下图的这种情况的判断，因为求最小深度的时候，我们的关键是找到第一个叶子结点 返回他的深度（即为二叉树最小深度）
而对于非叶子结点，我们要分三种情况讨论，只有左孩子，只有右孩子和左右孩子都有，根据下图可知，
1. 如果一个节点只有左孩子，那么他的深度就是（1+以左孩子为根的子树深度），
2. 同理可知如果一个节点只有右孩子，那么他的深度就是（1+以右孩子为根的子树深度），
3. 如果都有的话就取左右孩子为根的子树的最小深度。
3/ depth:应该是29
1、深度优先遍历（DFS）
根据上面的三种情况结合深度优先遍历的思想，我们能写出以下代码：
DFS 主要代码 c++
class Solution {
public:int minDepth(TreeNode *root) {
if(root==NULL) return 0;if(root->left==NULL) return 1 + minDepth(root->right); //如果只有右孩子if(root->right==NULL) return 1 + minDepth(root->left); // 如果只有左孩子return 1+min(minDepth(root->left),minDepth(root->right));}
};
2、用广度优先遍历（BFS）
在这里和求最大深度不同是，最大深度的目的是求出最后的层数返回即可。可是当我们求最小深度的时候，要明确，当我们遇到第一个叶子结点的时候就停止迭代，返回当前的层数，所以要在求二叉树最大深度的代码上加上一个判断（p->left == NULL && p->right==NULL），因为叶子节点没有后续的子节点，就可以作为最小的层数进行返回。
BFS 主要代码 c++
class Solution {
public:int minDepth(TreeNode *root){
if(root == NULL)return 0;int res = 0; // 标记高度最大值queue<TreeNode *> q;q.push(root);while(!q.empty())// 迭代操作标志{
++ res; // 每执行一层，深度+1。for(int i = 0, n = q.size(); i < n; ++ i) //对队列里的每个元素进行操作。{
TreeNode *p = q.front(); // 具体的队列操作是q.pop(); // 弹出根节点，然后放入孩子节点（如果有）if(p->left == NULL && p->right==NULL) return res;if(p -> left != NULL)q.push(p -> left);if(p -> right != NULL)q.push(p -> right);}}return res;}
};
补充python解法
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0dp = collections.deque([(root,1),]) #双边队列辅助while dp:cur, count = dp.popleft()if cur.right:dp.append((cur.right,count+1))if cur.left:dp.append((cur.left, count+1))if not cur.left and not cur.right:return count
总结
对于求树的深度的问题，一般情况下，我们可以用递归，非递归两种方法来求解，大都数情况下，结合DFS的思想可以很简单的写出递归的方案，但是合理利用队列进行层序遍历，也是一种十分高效的手段，并且代码也并不是很难理解，建议两个方法互相结合着看，推荐掌握BFS 非递归的方法，毕竟多熟悉熟悉队列的操作也没坏处~
最后不要忘记树是空的情况哦！！！。调了半天才发现这里也有个小坑
和 解答：leetcode 104. Maximum Depth of Binary Tree （求二叉树的最大深度,DFS,BFS）的一起理解效果会更好！！！！！！！！