#include "stdbool.h"
#define NULL ((void *)0)

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

//深度优先搜索
//时间复杂度：O(N)，其中 N 是树的节点数。对每个节点访问一次。
int minDepth(struct TreeNode* root){
    if(root==NULL)
        return 0;
    else if(root->left==NULL&&root->right==NULL)
        return 1;
    else if(root->left==NULL)
        return minDepth(root->right)+1;
    else if(root->right==NULL)
        return minDepth(root->left)+1;
    else
        return fmin(minDepth(root->left),minDepth(root->right))+1;
}