【二叉树】二叉树最小深度

做题思路：递归解决

1. 递归结束条件：传入结点为叶子结点，返回1
2. 进入左右子树找到最小路径，返回较小的路径

#define MAX 10000
int minDepth(struct TreeNode* root){
    if(!root)
        return 0;

    if(!root->left && !root->right)
        return 1;
    int left = MAX;
    int right = MAX;
    if(root->left)
        left = minDepth(root->left);
    if(root->right)
        right = minDepth(root->right);
    return left < right ? left+1 : right+1;
}

官方思路：递归解决

当结点只有一个子树时，最小路径为子树深度+1。若有两颗子树，则为较小子树的深度

1.递归结束条件：传入结点为NULL

2.若结点只有一个子树，返回那颗子树的深度

3.否则返回两颗子树深度较小的那个

int minDepth(struct TreeNode* root){
    if(!root)
        return 0;
    
    int left = minDepth(root->left);
    int right = minDepth(root->right);
    //当只有左子树时
    if(left && !right)
        return 1+left;
    //当只有右子树时
    if(!left && right)
        return 1+right;
    //当左右孩子都存在时
    return (left < right ? left : right)+1;
}

解题思路2：用队列迭代层序遍历解决

1.一层一层将二叉树入队

2.若本层有叶子结点，就返回深度

int minDepth(struct TreeNode* root){
    if(!root)
        return 0;
    
    struct TreeNode* queue[3000];
    int queue_front = 0;
    int queue_rear = 0;
    queue[queue_rear++] = root;

    int depth = 0;
    int levelLength = 0;

    while(levelLength = (queue_rear - queue_front)) {
        depth++;
        int i = 0;
        for(i = 0; i < levelLength; i++) {
            struct TreeNode* temp = queue[queue_front++];
            if(temp->left)
                queue[queue_rear++] = temp->left;
            if(temp->right)
                queue[queue_rear++] = temp->right;
            if(!temp->right && !temp->left)
                return depth;
        }
    }
    return -1;
}