二叉树最小深度：深度优先与广度优先解法

二叉树的最小深度是一个经典的算法问题，它涉及到二叉树的结构和遍历策略。在给定的PDF文件"16_二叉树的最小深度.pdf"中，主要讨论了如何找到一棵二叉树的最小深度，即从根节点到最近叶子节点的最短路径上的节点数量，其中叶子节点是没有子节点的节点。 方法一：深度优先搜索（DFS） 深度优先搜索是一种递归的策略，适用于这个问题。首先，我们需要检查根节点，如果根节点既是左子节点又是右子节点（即叶子节点），则最小深度为1。接着，对于非叶子节点，我们分别计算其左右子树的最小深度，并取两者中的较小值加1作为当前节点的最小深度。这种方法保证了每次都尽可能地深入探索，直到找到叶子节点。Java代码中，`Solution`类的`minDepth`方法就是基于这种思想实现的。 ```java public int minDepth(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; // 叶子节点 int min_depth = Integer.MAX_VALUE; if (root.left != null) min_depth = Math.min(min_depth, minDepth(root.left)); if (root.right != null) min_depth = Math.min(min_depth, minDepth(root.right)); return min_depth + 1; } ``` 时间复杂度分析：深度优先搜索的时间复杂度为O(N)，其中N是树的节点数，因为每个节点都会被访问一次。空间复杂度为O(H)，其中H是树的高度，最坏情况下（如完全不平衡的链状树）空间复杂度接近O(N)，而平均情况下，由于递归栈的深度通常与树的高度相关，空间复杂度接近O(logN)。 方法二：广度优先搜索（BFS） 另一种解决方案是使用广度优先搜索，从根节点开始，逐层遍历树，每次处理完一层再进行下一层，直到找到叶子节点。这样可以确保总是找到距离当前节点最近的叶子节点。Python实现可能类似于以下代码： ```python from collections import deque def minDepth(root): if root is None: return 0 queue = deque([(root, 1)]) while queue: node, depth = queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth + 1)) if node.right: queue.append((node.right, depth + 1)) # 如果没有叶子节点，这应该不会发生，但为了完整性，我们可以添加一个返回值 return -1 # 代表树为空或未找到叶子节点 ``` 在这个实现中，空间复杂度也是O(H)，因为广度优先搜索需要一个队列来存储每一层的节点。 总结来说，解决二叉树的最小深度问题，我们可以使用深度优先搜索或广度优先搜索两种策略，它们分别代表了递归和迭代的方式，虽然时间复杂度相同，但空间复杂度有所不同。理解这两种搜索方法并掌握它们的实现，有助于提高解决这类二叉树问题的能力。