当前位置：首页 > news >正文

LeeCode104. 二叉树的最大深度，LeeCode111. 二叉树的最小深度

news 2025/9/3 10:58:17

LeeCode104. 二叉树的最大深度

题目描述

给定一个二叉树的根节点 root，返回其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

思路解析

要计算二叉树的最大深度，我们可以采用递归的方法。因为二叉树的结构是递归定义的，所以递归非常适合这种问题。

具体来说，对于每一个节点，它的最大深度等于其左子树的最大深度和右子树的最大深度中的较大者，再加上当前节点本身（即 +1）。如果当前节点为空，则说明到达了叶子节点的下一层，此时深度为 0。

例如，对于如下二叉树：

    3/ \9  20/  \15   7

它的最大深度是 3（3 → 20 → 15 或 3 → 20 → 7）。

Java 实现

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}public class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}
}

这段代码非常简洁，逻辑清晰。通过递归调用，我们能够轻松地遍历整个树，并找到最大深度。

注意事项

当树为空时，返回 0。
如果只有一个根节点，那么最大深度是 1。
递归方法的时间复杂度是 O(n)，其中 n 是树中的节点总数。

LeeCode111. 二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。
最小深度是指从根节点到最近的叶子节点的最短路径上的节点数量。

思路解析

这道题与前一道题类似，但有一个关键的区别：叶子节点是指没有子节点的节点。因此，在计算最小深度时，不能简单地取左右子树的最小值，而是需要考虑是否存在空子树的情况。

比如，如果一个节点只有左子树而没有右子树，那么该节点的最小深度应该是左子树的最小深度加 1，而不是直接取左右子树的最小值。否则可能会误判为 0，导致错误。

因此，我们需要特别处理这种情况。

Java 实现

public class Solution {public int minDepth(TreeNode root) {if (root == null) {return 0;}// 如果左子树为空，只看右子树if (root.left == null) {return minDepth(root.right) + 1;}// 如果右子树为空，只看左子树if (root.right == null) {return minDepth(root.left) + 1;}// 否则取左右子树的最小值return Math.min(minDepth(root.left), minDepth(root.right)) + 1;}
}

这段代码通过判断左右子树是否为空，避免了因空子树而导致的错误计算。例如，当某个节点只有一个子树时，我们不会将其视为叶子节点，而是继续向下查找。

注意事项

当树为空时，返回 0。
如果只有一个根节点，那么最小深度是 1。
时间复杂度同样是 O(n)，空间复杂度取决于递归栈的深度。

三、最大深度 vs 最小深度

虽然这两道题都涉及二叉树的深度计算，但它们在处理方式上有明显差异。

特性	最大深度	最小深度
定义	根到最远叶子的节点数	根到最近叶子的节点数
处理空子树	可以忽略，直接取另一侧	必须特殊处理，避免误判
递归逻辑	直接比较左右子树	需要判断是否有空子树
应用场景	检查树的高度	检查树的“扁平”程度