力扣第104题用c语言解决

<think>好的，我现在需要帮用户寻找LeetCode第104题用C语言的解决方法。首先，我得确认一下题目内容。LeetCode 104题是“二叉树的最大深度”，也就是求一棵二叉树从根节点到最远叶子节点的最长路径上的节点数。 用户需要的是C语言的解决方案，所以我得回忆一下C语言中如何实现二叉树的结构以及相关的遍历方法。通常，二叉树在C语言中会用结构体来定义节点，包含值、左子节点和右子节点指针。 接下来，我需要考虑如何计算最大深度。常见的方法有递归和迭代两种。递归方法比较直观，因为二叉树本身是递归结构。最大深度等于左子树和右子树深度的较大者加一。这个思路应该可以很快写出来。 然后，我需要确认递归的终止条件。当节点为空时，深度为0，这应该是递归的基准情况。这样递归函数就能正确返回每个节点的深度。 对于C语言的具体实现，首先需要定义树节点的结构体，通常题目会给出，比如： struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; 然后，递归函数maxDepth会接收一个指向根节点的指针。如果根节点为空，返回0。否则，递归计算左右子树的深度，取较大者加一。 用户可能需要具体的代码示例，所以我得写出这个递归函数。另外，是否需要考虑非递归的方法？比如用层序遍历（BFS）来计算深度？虽然递归更简洁，但有时候面试中可能会问迭代的方法。不过用户可能更倾向于最简单的解法，所以先提供递归版本，如果有需要再补充迭代方法。 接下来，我需要检查代码是否正确。例如，当树为空时返回0，只有一个根节点时返回1，左右子树有不同深度时取最大值。这些情况都应该被正确处理。 另外，用户提供的引用中有一些LeetCode的问题链接，比如引用[1]和引用[2]，不过这些似乎和二叉树的问题无关，可能是用户之前引用的内容，暂时可以忽略，除非有相关的内容可以利用。不过在这个问题中，用户明确需要的是104题的解法，所以应该专注于该题本身。 最后，确保代码符合C语言的语法，比如函数声明、结构体的访问方式是否正确。例如，递归调用时使用left_depth = maxDepth(root->left); 这样的语句。 总结一下，解决步骤是： 1. 定义树节点结构体。 2. 实现递归函数，计算左右子树的最大深度。 3. 返回较大值加一。 这样应该就能得到正确的结果。现在需要把这些步骤用C语言代码写出来，并验证其正确性。</think>### LeetCode 104 二叉树的最大深度（C语言解法） #### 问题描述 给定一个二叉树，找出其最大深度（从根节点到最远叶子节点的最长路径上的节点数）[^1]。 #### 数据结构定义 ```c struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; ``` #### 递归解法 **核心思想**：二叉树的最大深度 = 左子树深度与右子树深度的较大值 + 1 **时间复杂度**：$O(n)$，每个节点仅访问一次 **空间复杂度**：$O(h)$，递归栈深度（$h$为树高度） ```c int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } int left_depth = maxDepth(root->left); int right_depth = maxDepth(root->right); return (left_depth > right_depth ? left_depth : right_depth) + 1; } ``` #### 非递归解法（BFS层序遍历） **核心思想**：使用队列逐层遍历，统计层数 **时间复杂度**：$O(n)$ **空间复杂度**：$O(n)$ ```c #include <stdlib.h> int maxDepth(struct TreeNode* root) { if (!root) return 0; struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000); int front = 0, rear = 0, depth = 0; queue[rear++] = root; while (front < rear) { int level_size = rear - front; depth++; for (int i = 0; i < level_size; i++) { struct TreeNode* node = queue[front++]; if (node->left) queue[rear++] = node->left; if (node->right) queue[rear++] = node->right; } } free(queue); return depth; } ``` #### 关键点解析 1. **递归基准条件**：空节点返回深度0 2. **递归分解**：问题拆解为左/右子树的子问题 3. **BFS实现技巧**：队列存储每层节点，通过`level_size`控制层遍历 --- ###