C++算法练习-day30——111.二叉树的最小深度
题目来源：. - 力扣（LeetCode）
题目思路分析与代码详解
题目描述
给定一个二叉树，找到其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
思路分析
- 递归方法：
- 如果根节点为空，则深度为0。
- 如果根节点没有左右子节点，则深度为1（叶子节点）。
- 否则，递归计算左子树和右子树的最小深度，取两者中的最小值，然后加1（加上根节点的深度）。
- 广度优先搜索（BFS）方法：
- 使用队列进行层次遍历，从根节点开始。
- 每一层遍历开始时，记录当前层的节点数量。
- 遍历当前层的所有节点，如果发现某个节点是叶子节点（没有左右子节点），则返回当前深度。
- 否则，将当前节点的左右子节点加入队列，继续下一层的遍历。
- 如果遍历完所有层仍未找到叶子节点，则返回0（实际上这种情况不会发生，因为至少根节点存在）。
代码:
递归方法：
class Solution {
public: int minDepth(TreeNode* root) { // 如果根节点为空，返回深度0 if(!root){return 0;} // 如果根节点没有左右子节点，返回深度1 if(!root->left && !root->right){return 1;} int Min=INT_MAX; // 初始化最小深度为最大整数 // 递归计算左子树的最小深度，并更新最小值 if(root->left){Min=min(minDepth(root->left),Min);} // 递归计算右子树的最小深度，并更新最小值 if(root->right){Min=min(minDepth(root->right),Min);} // 返回最小深度加1（加上根节点的深度） return ++Min; }
};广度优先搜索（BFS）方法：
class Solution {
public: int minDepth(TreeNode* root) { if(!root){return 0;} // 如果根节点为空，返回深度0 queue<TreeNode*> que; // 使用队列进行层次遍历 que.push(root); // 将根节点入队 int ans=1; // 初始化深度为1 while(!que.empty()){ // 当队列不为空时，继续遍历 int sz=que.size(); // 记录当前层的节点数量 while(sz>0){ // 遍历当前层的所有节点 TreeNode* pos=que.front(); // 取出队首节点 que.pop(); // 队首节点出队 // 如果当前节点是叶子节点，返回当前深度 if(!pos->left && !pos->right){ return ans; } // 如果当前节点有左子节点，将左子节点入队 if(pos->left){ que.push(pos->left); } // 如果当前节点有右子节点，将右子节点入队 if(pos->right){ que.push(pos->right); } --sz; // 当前层节点数量减1 } ans++; // 完成当前层遍历，深度加1 } return 0; // 实际上不会执行到这里，因为至少根节点存在 }
};知识点摘要
- 递归：
- 递归是一种解决问题的方法，函数直接或间接调用自身。
- 递归函数通常有一个或多个基准情况（base case），用于结束递归。
- 广度优先搜索（BFS）：
- BFS是一种遍历或搜索树或图的数据结构的算法。
- BFS从根节点开始，逐层遍历所有节点。
- 常用于寻找最短路径或最小深度等问题。
- 队列：
- 队列是一种先进先出（FIFO）的数据结构。
- 在BFS中，队列用于存储待访问的节点。
本题考察的是二叉树的最小深度计算，可以通过递归和广度优先搜索（BFS）两种方法解决。递归方法通过递归调用自身计算左右子树的最小深度，然后取最小值加1。BFS方法通过层次遍历，逐层检查节点，一旦发现叶子节点，立即返回当前深度。两种方法各有优劣，递归方法简洁明了，但可能面临栈溢出的问题；BFS方法更适合处理大型树结构，因为它使用了队列来存储待访问的节点，避免了深度过大的问题。在实际应用中，可以根据具体情况选择合适的方法。