这是 LeetCode 129 题 “求根节点到叶节点数字之和” 的 C语言 实现。解题思路深度优先搜索DFSC 语言中我们可以通过递归函数来实现 DFS传递累加值定义递归函数“dfs(struct TreeNode* node, int current_sum)”将当前路径组成的数字向下传递。计算当前节点值“new_sum current_sum * 10 node-val”。判断叶子节点若“node-left NULL node-right NULL”说明到了叶子节点直接返回“new_sum”。递归左右子树否则返回左子树和右子树的递归结果之和。LeetCode 风格核心代码#include stdlib.h// LeetCode 中 TreeNode 的定义// struct TreeNode {// int val;// struct TreeNode *left;// struct TreeNode *right;// };// 深度优先搜索辅助函数int dfs(struct TreeNode* node, int current_sum) {if (node NULL) {return 0;}// 计算从根到当前节点路径组成的数字 int new_sum current_sum * 10 node-val; // 如果是叶子节点返回该路径的数字 if (node-left NULL node-right NULL) { return new_sum; } // 递归左右子树并求和 return dfs(node-left, new_sum) dfs(node-right, new_sum);}// 主函数入口int sumNumbers(struct TreeNode* root) {return dfs(root, 0);}完整可运行示例含本地测试如果你想在本地如 GCC 编译器运行测试可以使用以下完整代码。代码中手动构建了示例二叉树并演示了如何调用“sumNumbers” 函数#include stdio.h#include stdlib.h// 二叉树节点定义struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};// 创建新节点struct TreeNode* createNode(int val) {struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode));node-val val;node-left NULL;node-right NULL;return node;}// 深度优先搜索int dfs(struct TreeNode* node, int current_sum) {if (node NULL) return 0;int new_sum current_sum * 10 node-val; if (node-left NULL node-right NULL) { return new_sum; } return dfs(node-left, new_sum) dfs(node-right, new_sum);}// 主函数int sumNumbers(struct TreeNode* root) {return dfs(root, 0);}// 释放树的内存void freeTree(struct TreeNode* root) {if (root NULL) return;freeTree(root-left);freeTree(root-right);free(root);}int main() {// 示例 1: [1,2,3]// 1// /// 2 3struct TreeNode* root1 createNode(1);root1-left createNode(2);root1-right createNode(3);printf(“示例1结果: %d\n”, sumNumbers(root1)); // 输出: 25freeTree(root1);// 示例 2: [4,9,0,5,1] // 4 // / \ // 9 0 // / \ // 5 1 struct TreeNode* root2 createNode(4); root2-left createNode(9); root2-right createNode(0); root2-left-left createNode(5); root2-left-right createNode(1); printf(示例2结果: %d\n, sumNumbers(root2)); // 输出: 1026 freeTree(root2); return 0;}编译与运行gcc sum_numbers.c -o sum_numbers./sum_numbers复杂度分析时间复杂度O(n)其中 n 是二叉树的节点总数每个节点被访问一次。空间复杂度O(h)其中 h 是二叉树的高度。主要是递归调用栈占用的空间最坏情况树退化为链表下为 O(n)。 代码说明为什么不用全局变量 上面的实现使用了函数返回值来累加避免了使用全局变量线程安全且更符合函数式编程风格。指针操作C 语言中通过“-” 访问结构体成员判断子树是否存在只需检查指针是否为“NULL”。需要我为你提供迭代法使用栈模拟 DFS的 C 语言实现或者帮你对比 C 与 Python/Rust 在递归处理上的差异吗
这是 LeetCode 129 题 “求根节点到叶节点数字之和” 的 C语言 实现。解题思路深度优先搜索DFSC 语言中我们可以通过递归函数来实现 DFS传递累加值定义递归函数“dfs(struct TreeNode* node, int current_sum)”将当前路径组成的数字向下传递。计算当前节点值“new_sum current_sum * 10 node-val”。判断叶子节点若“node-left NULL node-right NULL”说明到了叶子节点直接返回“new_sum”。递归左右子树否则返回左子树和右子树的递归结果之和。LeetCode 风格核心代码#include stdlib.h// LeetCode 中 TreeNode 的定义// struct TreeNode {// int val;// struct TreeNode *left;// struct TreeNode *right;// };// 深度优先搜索辅助函数int dfs(struct TreeNode* node, int current_sum) {if (node NULL) {return 0;}// 计算从根到当前节点路径组成的数字 int new_sum current_sum * 10 node-val; // 如果是叶子节点返回该路径的数字 if (node-left NULL node-right NULL) { return new_sum; } // 递归左右子树并求和 return dfs(node-left, new_sum) dfs(node-right, new_sum);}// 主函数入口int sumNumbers(struct TreeNode* root) {return dfs(root, 0);}完整可运行示例含本地测试如果你想在本地如 GCC 编译器运行测试可以使用以下完整代码。代码中手动构建了示例二叉树并演示了如何调用“sumNumbers” 函数#include stdio.h#include stdlib.h// 二叉树节点定义struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};// 创建新节点struct TreeNode* createNode(int val) {struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode));node-val val;node-left NULL;node-right NULL;return node;}// 深度优先搜索int dfs(struct TreeNode* node, int current_sum) {if (node NULL) return 0;int new_sum current_sum * 10 node-val; if (node-left NULL node-right NULL) { return new_sum; } return dfs(node-left, new_sum) dfs(node-right, new_sum);}// 主函数int sumNumbers(struct TreeNode* root) {return dfs(root, 0);}// 释放树的内存void freeTree(struct TreeNode* root) {if (root NULL) return;freeTree(root-left);freeTree(root-right);free(root);}int main() {// 示例 1: [1,2,3]// 1// /// 2 3struct TreeNode* root1 createNode(1);root1-left createNode(2);root1-right createNode(3);printf(“示例1结果: %d\n”, sumNumbers(root1)); // 输出: 25freeTree(root1);// 示例 2: [4,9,0,5,1] // 4 // / \ // 9 0 // / \ // 5 1 struct TreeNode* root2 createNode(4); root2-left createNode(9); root2-right createNode(0); root2-left-left createNode(5); root2-left-right createNode(1); printf(示例2结果: %d\n, sumNumbers(root2)); // 输出: 1026 freeTree(root2); return 0;}编译与运行gcc sum_numbers.c -o sum_numbers./sum_numbers复杂度分析时间复杂度O(n)其中 n 是二叉树的节点总数每个节点被访问一次。空间复杂度O(h)其中 h 是二叉树的高度。主要是递归调用栈占用的空间最坏情况树退化为链表下为 O(n)。 代码说明为什么不用全局变量 上面的实现使用了函数返回值来累加避免了使用全局变量线程安全且更符合函数式编程风格。指针操作C 语言中通过“-” 访问结构体成员判断子树是否存在只需检查指针是否为“NULL”。需要我为你提供迭代法使用栈模拟 DFS的 C 语言实现或者帮你对比 C 与 Python/Rust 在递归处理上的差异吗
