二叉树的最小深度是一个经典的算法问题,目标是找到从根节点到最近叶子节点的最短路径上所包含的节点数量。在这个问题中,叶子节点是指没有子节点的节点。解决这个问题有两种常见的方法:深度优先搜索(DFS)和广度优先搜索(BFS)。 我们来看深度优先搜索的解决方案。DFS是一种递归策略,它沿着树的分支尽可能深地搜索。在本题中,我们从根节点开始,如果根节点就是叶子节点(即没有子节点),那么最小深度就是1。如果根节点有子节点,我们将分别计算其左子树和右子树的最小深度,并取较小的那个值。通过递归调用这个过程,我们可以得到整棵树的最小深度。在Java中,这个算法可以这样实现: ```java class Solution { 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(minDepth(root.left), min_depth); } if (root.right != null) { min_depth = Math.min(minDepth(root.right), min_depth); } return min_depth + 1; } } ``` 这个算法的时间复杂度是O(N),因为每个节点都会被访问一次。空间复杂度是O(H),其中H是树的高度。在最坏的情况下,如果树呈链状,空间复杂度会达到O(N);而在平均情况下,由于树的高度通常与节点数的对数成正比,所以空间复杂度约为O(logN)。 另一种方法是使用广度优先搜索。BFS是从根节点开始,按层序遍历树的节点。当找到第一个叶子节点时,它的深度就是最小深度。BFS通常使用队列来存储待访问的节点。在Python中,我们可以这样实现: ```python class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 if not root.left and not root.right: return 1 min_depth = 10**9 queue = [(root, 1)] while queue: node, depth = queue.pop(0) 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)) ``` 同样,这个算法的时间复杂度也是O(N),因为每个节点都会被访问一次。空间复杂度是O(H),这里使用队列存储待访问节点,最坏情况下空间复杂度为O(N),平均情况下为O(logN)。 这两种方法各有优劣。DFS在处理某些特定结构的树时可能会更快,因为它不需要额外的数据结构来存储中间结果,但可能会消耗更多的栈空间。而BFS则能保证找到第一个叶子节点的最小深度,但需要额外的队列空间。选择哪种方法取决于具体的应用场景和资源限制。
- 粉丝: 37
- 资源: 28
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助