C语言完整给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 【输入形式】 二叉树的先序扩展序列(字符串表示,以#填充空结点) 【输出形式】 所有数字之和 【样例输入】 495##1##0## 【样例输出】 1026
时间: 2024-03-09 20:46:55 浏览: 103
C语言实现二叉树的各种操作。
4星 · 用户满意度95%
以下是使用 C 语言实现的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Definition for a binary tree node.
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;
}
// 根据先序遍历序列构建二叉树
struct TreeNode* buildTree(char* s, int* index) {
if (s[*index] == '#') {
(*index)++;
return NULL;
}
int val = 0;
while (s[*index] != '\0' && s[*index] != '#') {
val = val * 10 + (s[*index] - '0');
(*index)++;
}
struct TreeNode* node = createNode(val);
node->left = buildTree(s, index);
node->right = buildTree(s, index);
return node;
}
// 计算从根节点到叶节点生成的所有数字之和
int sumNumbers(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int totalSum = 0;
dfs(root, 0, &totalSum);
return totalSum;
}
// 深度优先搜索算法
void dfs(struct TreeNode* node, int pathSum, int* totalSum) {
pathSum = pathSum * 10 + node->val;
if (node->left == NULL && node->right == NULL) {
*totalSum += pathSum;
}
if (node->left != NULL) {
dfs(node->left, pathSum, totalSum);
}
if (node->right != NULL) {
dfs(node->right, pathSum, totalSum);
}
}
int main() {
char s[100];
scanf("%s", s);
int index = 0;
struct TreeNode* root = buildTree(s, &index);
int result = sumNumbers(root);
printf("%d\n", result);
return 0;
}
```
在上面的代码中,我们定义了一个 `createNode` 函数,用于创建一个新的二叉树节点。我们还定义了一个 `buildTree` 函数,用于根据先序遍历序列构建二叉树。在 `buildTree` 函数中,我们首先判断当前字符是否为 `#`,如果是,则返回空节点;否则,我们按照数字字符的顺序构建二叉树节点,并递归构建左右子树。
接下来,我们调用 `sumNumbers` 函数来计算从根节点到叶节点生成的所有数字之和。在 `sumNumbers` 函数中,我们判断根节点是否为空,如果为空,则直接返回 0。否则,我们定义了一个 `totalSum` 变量,用于记录所有路径数字之和的总和。我们通过调用 `dfs` 函数来计算每个叶节点所表示的数字,并将其加入到 `totalSum` 中。
在 `dfs` 函数中,我们首先将当前节点的值加入到 `pathSum` 变量中,并将 `pathSum` 乘以 10,以便计算下一个节点的路径数字。如果当前节点是叶节点,则将 `pathSum` 加入到 `totalSum` 中。最后,我们递归遍历左右子树,分别调用 `dfs` 函数,并将 `pathSum` 和 `totalSum` 作为参数传递进去。
最后,我们在 `main` 函数中读入先序遍历序列,根据先序遍历序列构建二叉树,并调用 `sumNumbers` 函数计算所有数字之和,并输出结果。
阅读全文