1 /*
 2  * @lc app=leetcode.cn id=111 lang=cpp
 3  *
 4  * [111] 二叉树的最小深度
 5  */
 6 
 7 // @lc code=start
 8 /**
 9  * Definition for a binary tree node.
10  * struct TreeNode {
11  *     int val;
12  *     TreeNode *left;
13  *     TreeNode *right;
14  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
15  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
16  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17  * };
18  */
19 class Solution {
20 public:
21     /*
22     终止条件、返回值和递归过程：
23 1）当前节点root为空时，说明此处树的高度为0，0也是最小值。
24 2）当前节点root的左子树和右子树都为空时，说明此处树的高度为1，1也是最小值。
25 3）如果为其他情况，则说明当前节点有值，且需要分别计算其左右子树的最小深度，返回最小深度+1，+1表示当前节点存在有1个深度。
26 时间复杂度：O(n)，n为树的节点数量。
27     */
28     int minDepth(TreeNode* root) {
29          //当前节点root为空时，说明此处树的高度为0，0也是最小值
30         if(!root) return 0;
31         //当到达叶子节点时，叶子节点的深度为1
32        if(root->left==nullptr&&root->right==nullptr) return 1;
33        int m=INT_MAX;
34        //如果为其他情况，则说明当前节点有值，且需要分别计算其左右子树的最小深度，返回最小深度+1，+1表示当前节点存在有1个深度
35        if(root->left!=nullptr) m=min(minDepth(root->left),m);
36        if(root->right!=nullptr) m=min(minDepth(root->right),m);
37        return m+1;
38     }
39 };
40 // @lc code=end