【LeetCode 104】二叉树的最大深度（C语言详解 | 递归 + BFS）
一、题目描述
给定一个二叉树root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：3示例 2：
输入：root = [1,null,2] 输出：2二、解题思路
这道题是二叉树中的入门经典题，核心思想非常简单：
👉最大深度 = 1 + max(左子树深度, 右子树深度)
1️⃣ 递归思路（DFS）
从根节点开始：
如果当前节点为空，深度为
0否则：
递归求左子树深度
递归求右子树深度
取较大值 + 1
2️⃣ 递归过程理解
假设树如下：
3 / \ 9 20 / \ 15 7递归过程类似：
maxDepth(3) = 1 + max(maxDepth(9), maxDepth(20)) maxDepth(9) = 1 maxDepth(20) = 1 + max(1,1) = 2 最终结果 = 1 + max(1,2) = 3三、代码实现（C语言）
✅ 方法一：递归（推荐）
int maxDepth(struct TreeNode* root) { if (root == NULL) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return (left > right ? left : right) + 1; }四、非递归解法（层序遍历 BFS）
除了递归，还可以用队列进行层序遍历。
思路：
每遍历一层，深度 +1
使用队列存储每一层节点
✅ 方法二：BFS（队列实现）
#include <stdlib.h> int maxDepth(struct TreeNode* root) { if (root == NULL) return 0; struct TreeNode* queue[10000]; int front = 0, rear = 0; queue[rear++] = root; int depth = 0; while (front < rear) { int size = rear - front; // 当前层节点数 depth++; for (int i = 0; i < size; i++) { struct TreeNode* node = queue[front++]; if (node->left) queue[rear++] = node->left; if (node->right) queue[rear++] = node->right; } } return depth; }五、复杂度分析
递归（DFS）
时间复杂度：
O(n)空间复杂度：
O(h)（树高）
BFS
时间复杂度：
O(n)空间复杂度：
O(n)（队列）
六、总结
| 方法 | 优点 | 缺点 |
|---|---|---|
| 递归（DFS） | 代码简洁，思路清晰 | 可能栈溢出 |
| BFS（层序） | 直观体现“层数” | 需要额外队列 |
七、扩展思考
这题是很多二叉树问题的基础模型：
✅ 判断平衡二叉树（110）
✅ 二叉树最小深度（111）
✅ 路径相关问题
👉 核心套路：
“当前节点 = 子问题的组合”