难度简单943收藏分享切换为英文接收动态反馈
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5提示：
- 树中节点数的范围在
[0, 105]内 -1000 <= Node.val <= 1000
1、深度优先遍历
先说明一下，这道题虽说和 104. 二叉树的最大深度 有一些关系，但是直接将其思路搬过来的话会有一些错误，就是这道题要求的是最小深度，那么可能存在一开始的根节点等没有左孩子，也就是可能只有右孩子，此时如果按照最大深度的思想也就是判断左右子树的最小个数的话，那么可能会误以为最小深度为 1，但是其实最小深度还得看是否是叶子节点！
这就重新审题了，题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！
其实只需要加上一些判断即可！
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr)
return 0;
int leftHeight = minDepth(root->left);
int rightHeight = minDepth(root->right);
// 其中一个为空则返回另一个子树的高度！
if(root->left == nullptr && root->right != nullptr)
return rightHeight + 1;
if(root->left != nullptr && root->right == nullptr)
return leftHeight + 1;
// 都不为空才返回其最小高度！
return min(leftHeight, rightHeight) + 1;
}
};2、广度优先遍历
其实就是迭代法，借助到队列来实现！
其中要点就是找到每一层中出现的第一个叶子节点，则说明此层就是最小深度的那一层！
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> qe;
if(root != nullptr)
qe.push(root);
int depth = 0;
while(!qe.empty())
{
int size = qe.size();
depth++;
for(int i = 0; i < size; ++i)
{
TreeNode* node = qe.front();
qe.pop();
if(node->left != nullptr)
qe.push(node->left);
if(node->right != nullptr)
qe.push(node->right);
// 返回的关键点：叶子节点则返回
if(node->left == nullptr && node->right == nullptr)
return depth;
}
}
return depth;
}
};