111.给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

1. 通过层次遍历，只要找到有一个结点的左右结点都为空时，就返回此时的层数，即为最小深度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int minDepth(struct TreeNode* root){
    if (root == NULL)
        return 0;
    struct TreeNode* queue[10000];
    int front = 0, rear = 0, pre_rear;
    queue[rear] = root;
    int depth = 0;
    while (front <= rear) {
        pre_rear = rear;
        depth++;
        while (front <= pre_rear) {
            struct TreeNode* p = queue[front++];
            if (p->left == NULL && p->right == NULL)
                return depth;
            if (p->left != NULL)
                queue[++rear] = p->left;
            if (p->right != NULL)
                queue[++rear] = p->right;
        }
    }
    return depth;
}

2. 另一种解法是递归法。递归地求出左右子树的最小深度，取小的那一个然后加1就是所求结果。注意该递归写法跟求最大深度其实是一样的，不过中间增加了两个判断，用来针对两种情况：左子树为空右子树不为空以及左子树部位空右子树为空；如果不加判断的话，则会出现以根节点所在层数为最小深度的情况。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int minDepth(struct TreeNode* root){
    if (root == NULL)
        return 0;
    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);
    if (root->left == NULL && root->right != NULL)
        return 1 + rightDepth;
    if (root->left != NULL && root->right == NULL)
        return 1 + leftDepth;
    return leftDepth <= rightDepth ? leftDepth + 1: rightDepth + 1;
}