--- tags: ["LeetCode", "二叉树", "深度优先搜索", "广度优先搜索", "递归", "简单"] create time: 2026-05-17 10:30 --- # 37-二叉树的最大深度 ## 题面 给定一个二叉树 `root`，返回其**最大深度**。 二叉树的 **最大深度** 是指从根节点到最远叶子节点的最长路径上的节点数。 > [!info] 💡 核心概念：什么是「深度」？ > - 根节点的深度为 **1** > - 每往下一层，深度 **+1** > - 「最大深度」= 从根到**最远叶子节点**经过的节点总数 > > > [!question] 🤔 思考：深度和高度有什么区别？ > > - **深度（Depth）**：从根节点到当前节点的距离（自顶向下计数） > > - **高度（Height）**：从当前节点到最远叶子节点的距离（自底向上计数） > > - 根节点的高度 = 整棵树的最大深度，这是一个重要等价关系！ **示例 1：** ``` 输入：root = [3,9,20,null,null,15,7] 输出：3 解释： 3 深度为 1 / \ ┌─────────────┐ 9 20 │ 最长路径：3→20→15 或 3→20→7 │ │ 共 3 个节点，故深度为 3 │ / \ └─────────────┘ 15 7 ``` **示例 2：** ``` 输入：root = [1,null,2] 输出：2 解释：树退化为链状 1→2，深度为 2 ``` **约束：** - 树中节点的数量在 `[0, 10^4]` 区间内 - `-100 <= Node.val <= 100` --- ## 思路 ### 方法一：深度优先搜索 DFS（递归）⭐⭐ #### 核心洞察 > [!question] 💡 思考 > 对于任意一棵子树，它的最大深度等于什么？假设你已经知道左子树深度是 `L`、右子树深度是 `R`，那么这棵树的深度是多少？ 答案一目了然：**`max(L, R) + 1`**。这个 `+1` 就是当前根节点自身。 这是典型的**自底向上**计算：先求出左右子树的答案，再合并得到当前结果。 #### 递归三要素 | 要素 | 内容 | |------|------| | **终止条件** | 节点为空时，深度为 0 | | **递归表达式** | `depth(node) = max(depth(node.left), depth(node.right)) + 1` | | **返回值** | 以 `node` 为根的树的深度 | #### 执行流程图 ```mermaid flowchart TD A["maxDepth(3)"] --> B["maxDepth(9)"] B --> C["maxDepth(nil) → 0"] B --> D["maxDepth(nil) → 0"] B --> E["max(0,0)+1 = 1 ✅"] A --> F["maxDepth(20)"] F --> G["maxDepth(15)"] G --> H["maxDepth(nil) → 0"] G --> I["maxDepth(nil) → 0"] G --> J["max(0,0)+1 = 1 ✅"] F --> K["maxDepth(7)"] K --> L["maxDepth(nil) → 0"] K --> M["maxDepth(nil) → 0"] K --> N["max(0,0)+1 = 1 ✅"] F --> O["max(1,1)+1 = 2 ✅"] A --> P["max(1,2)+1 = 3 ✅"] style E fill:#d4edda style N fill:#d4edgreen style O fill:#cce5ff style P fill:#f8d7da,stroke:#721c24 ``` > [!note] 🧠 递归的执行视角 > 想象一下：每个调用帧都在等待子调用的返回值，就像每个人都在等下属报业绩后再决定自己的绩效。直到遇到空节点（叶子之下），返回值逐层冒泡上来，层层累加 `+1`，最终算出整棵树的深度。 #### 为什么正确？ 利用数学归纳法可以证明： - **基准情况**：空树深度为 0 ✅ - **归纳步骤**：假设所有高度小于 `h` 的子树都能正确返回深度，那么高度为 `h` 的树取其左右子树深度的最大值再加 1，显然也正确 ✅ ### 方法二：广度优先搜索 BFS（层序遍历）⭐ 除了「自底向上」的递归思路，还可以「自顶向下」逐层扫描——这正是 BFS 的拿手好戏。 #### 核心思想 BFS 天然按层访问节点。**遍历了多少层，树的深度就是多少。** ```mermaid flowchart LR A["层1: [3]"] -->|"深度 = 1"| B["层2: [9, 20]"] B -->|"深度 = 2"| C["层3: [15, 7]"] C -->|"深度 = 3"| D["无更多层\n返回 3 ✅"] style A fill:#e8f5e9 style B fill:#fff3e0 style C fill:#e3f2fd style D fill:#fce4ec ``` #### 算法骨架 ``` 初始化队列 queue，放入 root depth = 0 while queue 非空: depth++ // 又扫完了一层 n = queue.length // 固定当前层的节点数 for i from 0 to n-1: // 只处理当前层的节点 node = queue.pop() if node.left != nil: push queue, node.left if node.right != nil: push queue, node.right return depth ``` > [!warning] ⚠️ 关键细节 > 每一层开始前必须先记录 `n = queue.length`！如果直接在 `for` 循环里判断 `len(queue) > 0`，会因为子节点不断入队而导致死循环。 #### DFS vs BFS 如何选择？ > [!comparison] ⚖️ 深度优先 vs 广度优先 > | 维度 | DFS（递归） | BFS（层序遍历） | > |------|------------|----------------| > | 代码简洁度 | ⭐⭐⭐ 仅需 3 行核心逻辑 | ⭐⭐ 需维护队列和层计数器 | > | 空间复杂度 | O(h)，递归栈深度 | O(w)，队列最多存一层宽度 | > | 实际效率 | 递归有函数调用开销 | 迭代，无调用开销 | > | 适用场景 | 通用解法，面试首选 | 需要按层处理问题时自然得出 | > [!tip] 🔑 何时选哪种？ > - 如果只问最大深度：**DFS 更简洁**，直接 return max(left, right) + 1 > - 如果问「每层最大值」「锯齿形遍历」等按层相关的问题：**BFS 天然适合** > - 面试中两者都可以，DFS 通常更高效因为不需要额外维护队列结构 --- ## 代码提示 ### DFS 伪代码 ``` func maxDepth(node): if node == nil: return 0 left = maxDepth(node.left) // 左子树深度 right = maxDepth(node.right) // 右子树深度 return max(left, right) + 1 // 取较大者 + 当前节点 ``` ### BFS 伪代码 ``` if root == nil: return 0 queue = [root] depth = 0 while len(queue) > 0: depth++ n = len(queue) for i from 0 to n-1: // 只处理当前层的节点 node = pop queue if node.left != nil: push queue, node.left if node.right != nil: push queue, node.right return depth ``` --- ## 技巧 > [!tip] 🔑 最大深度 = 最大高度（根节点视角） > 这道题本质上求的是「根节点的高度」。反过来想，**最小深度**则是「根到最近叶子节点」的距离。注意最小深度要求叶子节点（左右子树都为空），不能把有一侧子树为空的情况也算作叶子。 > [!tip] 🔑 一句代码搞定（Go 语言） > ```go > func maxDepth(root *TreeNode) int { > if root == nil { return 0 } > return imax(maxDepth(root.Left), maxDepth(root.Right)) + 1 > } > ``` > Go 标准库没有 `max` 泛函数（截至 1.21），需要自己写一个辅助函数或用 `if` 判断。Go 1.21+ 的 `slices.Max` 仅适用于切片，不适用于两个标量比较。 > [!note] 📊 复杂度速查 > | 方法 | 时间复杂度 | 空间复杂度 | > |------|-----------|-----------| > | DFS 递归 | **O(n)** — 每个节点访问一次 | **O(h)** — h 为树高，最坏 O(n)（链状），平均 O(log n)（平衡树） | > | BFS 迭代 | **O(n)** — 每个节点入队出队各一次 | **O(w)** — w 为树的最大宽度，最坏 O(n)（满二叉树最后一层） | > [!info] 🧩 延伸思考 > 如果把「最大深度」改成「直径」（任意两节点间的最长路径），思路会如何变化？答案是在每个节点同时记录「深度」和「经过该节点的最长路径」，用全局变量实时更新最大值。见 LeetCode 543. 二叉树的直径。 --- ## 代码 ### DFS 递归法（推荐）⭐⭐ ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxDepth(root *TreeNode) int { // 终止条件：空节点的深度为 0 if root == nil { return 0 } // 递归求左右子树的深度 left := maxDepth(root.Left) // 左子树深度 right := maxDepth(root.Right) // 右子树深度 // 当前节点深度 = 较深子树 + 1 if left > right { return left + 1 } return right + 1 } // 辅助函数：求两个整数的较大值 // Go 1.21 以下没有内置 max(int, int)，需自行实现 func max(a, b int) int { if a > b { return a } return b } ``` > [!success] ✅ 运行验证 > 这是 LeetCode 第 104 题，通过率约 73%。作为二叉树入门第一题，它完美展示了递归的「分而治之」思想：**将大问题拆解为相同形式的子问题**，直到触及最简单的边界（空节点）。 ### BFS 层序遍历法（参考）⭐ ```go /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxDepth(root *TreeNode) int { if root == nil { return 0 } var queue []*TreeNode // 使用切片模拟队列 queue = append(queue, root) depth := 0 for len(queue) > 0 { n := len(queue) // 固定当前层的节点数量 depth++ // 遍历了一层，深度 +1 for i := 0; i < n; i++ { node := queue[0] // 出队 queue = queue[1:] // 切片弹出首部 if node.Left != nil { queue = append(queue, node.Left) // 左孩子入队 } if node.Right != nil { queue = append(queue, node.Right) // 右孩子入队 } } } return depth } ``` > [!note] 🐹 Go 队列优化提示 > 上述 BFS 使用 `queue = queue[1:]` 出队，但切片头部不断删除会导致底层数组无法释放，内存只增不减。在实际工程中可以用双指针（head/tail 索引）避免缩容；但在这道题的数据范围（≤ 10^4 节点）下，两种写法差异可忽略，教学场景以最清晰为准。