题目链接
力扣网111 二叉树的最小深度
题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2示例 2：
代码语言：javascript复制输入：root = [2,null,3,null,4,null,5,null,6]
输出：5提示：
- 树中节点数的范围在
[0, 105]内 -1000 <= Node.val <= 1000
思路分析
知识点：递归
解析：
首先理解，最小深度是从根节点到最近叶子节点的最短路径上的节点数量。那我们可以设置这样的递归规则：
当左孩子和右孩子同时为空时，返回1，说明碰到了叶子结点，如果其中一个结点不为空或者同时存在，先从左孩子开始递归，左孩子完到右孩子，直到找到叶子结点返回。
接着实现大小的问题，我们分别将左右孩子递归的结果用一个变量保存，再找出最小的就可以了。
代码语言：javascript复制/**
* 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;
}
if(root->left==NULL&&root->right==NULL)//叶子结点的返回条件
{
return 1;
}
int ret=32767;//整型的最大值
if(root->left!=NULL)
{
ret=fmin(minDepth(root->left),ret);//相当于保存第一次递归的结果
}
if(root->right!=NULL)
{
ret=fmin(minDepth(root->right),ret);//再将第二次递归的结果找出，与上一次的进行比较，取最小值
}
return ret 1;//记得加上根节点返回
}
