leetcode-go/二叉树/37-二叉树的最大深度.md

tags, create time

tags	create time
LeetCode 二叉树 深度优先搜索 广度优先搜索 递归 简单	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 为根的树的深度

执行流程图

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 天然按层访问节点。遍历了多少层，树的深度就是多少。

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 语言）

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 递归法（推荐）⭐⭐

/**
 * 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 层序遍历法（参考）⭐

/**
 * 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 节点）下，两种写法差异可忽略，教学场景以最清晰为准。