二叉树--求最小深度（迭代和递归）
使用了两种解法，递归法和迭代法。
两种方法的对比总结
DFS (方法一
minDepth):特点: 代码简洁，逻辑通过
max巧妙处理了单链树的情况。缺点: 必须遍历完所有的分支才能确定谁最小。如果树严重左偏或右偏，栈深度较大。
BFS (方法二
levelOrder):特点: 利用队列层序遍历。
优点:效率更高。因为它只要找到第一个叶子节点就直接
return depth了，不需要像 DFS 那样把深处的节点也遍历一遍。在求“最短路径”或“最小深度”类问题时，BFS 通常是首选。
递归法
注意：如果左子树为空（left=0）或右子树为空（right=0），说明这不是叶子节点（最小深度要找到叶子节点），我们不能取 min（因为 min 会取到 0），必须取非空的那一侧（即 max）。
代码
// ========================================== // 方法一：递归法 (DFS - 后序遍历) // 核心思想：分别求左右子树深度，处理单支情况，最后取最小值 // ========================================== int minDepth(TreeNode* root) { if (root == NULL) return 0; // 终止条件 // 递归计算左右子树的深度 int left = minDepth(root->left); int right = minDepth(root->right); // 【关键逻辑】 // 如果左子树为空（left=0）或右子树为空（right=0），说明这不是叶子节点， // 我们不能取 min（因为 min 会取到 0），必须取非空的那一侧（即 max）。 // 例如：树 1->2，根节点 1 不是叶子，必须走 2 那边。 if (left == 0 || right == 0) { return max(left, right) + 1; } // 左右都不为空，说明是正常的左右分支，取最小的一边 + 根节点 1 return min(left, right) + 1; }迭代法
使用层序遍历，一层一层往下找，一旦遇到第一个“叶子节点”，马上返回深度。
代码
// ========================================== // 方法二：迭代法 (BFS - 广度优先搜索) // 核心思想：一层一层往下找，一旦遇到第一个“叶子节点”，马上返回深度。 // 优点：对于求最小深度，这通常比 DFS 更快，因为它不需要遍历整棵树。 // ========================================== int minDepthBFS(TreeNode* root) { int depth = 0; queue<TreeNode*> q; if (root) q.push(root); while (!q.empty()) { int size = q.size(); // 记录当前层有多少个节点 depth++; // 开始处理新的一层，深度 +1 for (int i = 0; i < size; i++) { TreeNode* node = q.front(); q.pop(); // 【核心优化】 // 如果当前节点没有左孩子且没有右孩子，说明它是我们遇到的 // “层级最浅”的叶子节点。直接返回当前深度，无需继续遍历！ if (node->left) q.push(node->left); if (node->right) q.push(node->right); if (!node->left && !node->right) return depth; // 找到最近的叶子，直接返回结果 } } return depth; }