https://leetcode.cn/problems/minimum-depth-of-binary-tree/
一、题目解析
给定一棵二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数。叶子节点是指没有左子节点和右子节点的节点。
以 [3,9,20,null,null,15,7] 为例：
plain text
3 / \ 9 20 / \ 15 7根节点 3 的左子节点 9 是叶子，路径 3→9 深度为 2。另一条路径 3→20→15（或 3→20→7）深度为 3。最小深度是 2。
如果用深度优先，可能先走完最长路径才回溯到最短路径。而广度优先（BFS）逐层扫描，第一次遇到叶子节点时所在的层数即最小深度——因为 BFS 保证先访问的节点离根更近。
二、BFS 层序遍历
用队列做层序遍历。每处理完一层，深度 +1。在每层中逐个取出节点，检查是否为叶子。一旦发现叶子，直接返回当前深度——这就是最短路径。
三、代码实现
java
class Solution { public int minDepth(TreeNode root) { // 空树深度为 0 if (root == null) { return 0; } // BFS 队列 Deque<TreeNode> queue = new ArrayDeque<>(); queue.add(root); int ans = 0; while (!queue.isEmpty()) { ans++; // 进入新的一层 int size = queue.size(); // 当前层的节点数 while (size-- > 0) { TreeNode cur = queue.pollFirst(); // 遇到叶子节点，当前层就是最短路径 if (cur.left == null && cur.right == null) { return ans; } // 子节点入队，进入下一层 if (cur.left != null) { queue.addLast(cur.left); } if (cur.right != null) { queue.addLast(cur.right); } } } return ans; }}时间复杂度 O(n)，每个节点最多入队一次。空间复杂度 O(n)，队列最坏存一整层节点。
本文由 AgentPlanFlow 生成