LeetCode 题解 | 104. 二叉树的最大深度
最新回答
人家有伞，我有大头。
2026-03-28 20:37:24
LeetCode 104. 二叉树的最大深度题解如下：
- 递归法：通过递归遍历左右子树，取较大值加1作为当前深度。
- 迭代法：利用栈模拟DFS，记录节点及其深度，迭代更新最大深度。
两种方法时间复杂度均为O(N)，递归法空间复杂度取决于树高，迭代法空间复杂度为O(N)。
方法一：递归算法思路：
- 基本情况：若根节点为空，返回深度0。
- 递归步骤：分别计算左右子树的深度，取较大值并加1（当前节点）。
Java代码：
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; }}Python代码：
class Solution: def maxDepth(self, root): if not root: return 0 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) return max(left_depth, right_depth) + 1复杂度分析：
- 时间复杂度：O(N)，每个节点访问一次。
- 空间复杂度：
最坏情况（树退化为链表）：O(N)。
最好情况（完全平衡树）：O(logN)。
算法思路：
- 使用栈存储节点及其当前深度，初始时栈包含根节点（深度1）。
- 弹出栈顶节点，更新最大深度，并将其子节点（深度+1）压入栈。
- 重复直到栈为空。
Java代码：
import javafx.util.Pair;import java.util.LinkedList;import java.util.Queue;class Solution { public int maxDepth(TreeNode root) { Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>(); if (root != null) { stack.add(new Pair<>(root, 1)); } int depth = 0; while (!stack.isEmpty()) { Pair<TreeNode, Integer> current = stack.poll(); root = current.getKey(); int currentDepth = current.getValue(); if (root != null) { depth = Math.max(depth, currentDepth); stack.add(new Pair<>(root.left, currentDepth + 1)); stack.add(new Pair<>(root.right, currentDepth + 1)); } } return depth; }}Python代码：
class Solution: def maxDepth(self, root): stack = [] if root: stack.append((1, root)) depth = 0 while stack: current_depth, root = stack.pop() if root: depth = max(depth, current_depth) stack.append((current_depth + 1, root.left)) stack.append((current_depth + 1, root.right)) return depth复杂度分析：
- 时间复杂度：O(N)，每个节点处理一次。
- 空间复杂度：O(N)，栈中最多存储所有节点。
- 递归法简洁直观，适合理解树的结构。
- 迭代法通过显式栈避免递归开销，适合深度较大的树。
根据树的结构和编程环境选择合适方法。递归法在平衡树中空间效率更高，而迭代法在极端情况下更稳定。
热门标签
