力扣111- 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。 示例 1：
bin1.png
输入：root = [3,9,20,null,null,15,7] 输出：2 示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5
提示：
树中节点数的范围在 [0, 10^5] 内 -1000 <= Node.val <= 1000
解法1：BFS深度优先遍历
这道题有几种解法，可以使用BFS优先遍历的方法解决。 用maxDepth表示二叉树的最小深度 使用一个队列先保存上一次节点，最开始就是root根节点，然后将root方法一个空的队列中。当队列不为空时，依次从队首获取元素，然后将队首的元素的左右节点(如果不为空)加入队列中，再将队首元素弹出，这样循环往复，在弹出当前层节点的过程中，同时将下层节点放入队列中，此时二叉树的深度加1，如果当前队首元素的左右节点均为空，则返回maxDepth;
C 实现代码：
代码语言：javascript复制/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// BFS优先搜索求解
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
std::deque<TreeNode *> bfsDeque;
int maxDepth = 1; // 默认根节点为1层
bfsDeque.push_back(root);
while (!bfsDeque.empty()) {
int szLen = bfsDeque.size();
// 将当前队列中的所有节点向下扩散
for (int i = 0; i < szLen; i ) {
// 取出当前队列首元素
TreeNode* frontNode = bfsDeque.front();
bfsDeque.pop_front();
// 判断是否到达终点
if (frontNode->left == nullptr && frontNode->right == nullptr) {
return maxDepth;
}
// 将 frontNode 的左右节点加入队列
if (frontNode->left != nullptr) {
bfsDeque.push_back(frontNode->left);
}
if (frontNode->right != nullptr) {
bfsDeque.push_back(frontNode->right);
}
}
// 遍历完每一层元素，深度加1
maxDepth ;
}
return maxDepth;
}
};解法2：递归法
同样也是递归法，主要就是确定单层的逻辑，和最大深度不一样的是，最小深度的条件限制比较多，如下图所示
test02.png
因此我们需要分类讨论，节点的孩子情况，因为这涉及到我们如何进行递归求解。 C 代码实现如下：
代码语言：javascript复制class Solution {
public:
int GetMinDepth(TreeNode* root)
{
if(root==nullptr)
{
return 0;
}
int leftdepth = GetMinDepth(root->left);
int rightdepth = GetMinDepth(root->right);
// 假如只有左孩子 那么返回左孩子的深度
if(root->left!=nullptr && root->right==nullptr)
{
return 1 leftdepth;
}
// 假如只有右孩子返回右孩子的深度
if(root->left==nullptr && root->right!=nullptr)
{
return 1 rightdepth;
}
// 加一是为了加当前的根节点
int depth = std::min(leftdepth, rightdepth) 1;
return depth;
}
int minDepth(TreeNode* root) {
return GetMinDepth(root);
}
};
