求二叉树根节点到指定数字对应结点的路径上数字组成的字符串,数字间空格隔开,用C语言编程
时间: 2024-11-18 13:27:25 浏览: 30
在C语言中,解决这个问题可以采用深度优先搜索(DFS)算法遍历二叉树,并记录路径上的数字。以下是基本的步骤:
1. 定义一个结构体表示二叉树节点,包含整数值和左右子节点指针。
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
2. 编写一个辅助函数`preorderTraversal`,用于递归地访问每个节点并记录路径。这个函数会检查当前节点是否为目标值,如果是,则将路径加入结果字符串;然后分别处理左、右子节点。
```c
void preorderTraversal(TreeNode* root, char* path, int target, int nodeIndex) {
if (root == NULL)
return;
// 将当前节点的值转换为字符串并追加到path
char num[50];
sprintf(num, "%d", root->val);
strcat(path, num);
// 如果到达目标节点,结束路径记录
if (root->val == target)
return;
// 递归处理左、右子节点,加上逗号作为分隔符
path[strlen(path)] = ',';
strcat(path, " ");
preorderTraversal(root->left, path, target, ++nodeIndex);
preorderTraversal(root->right, path, target, nodeIndex);
}
```
3. 主函数`findPath`接收树的根节点、目标值和结果字符串变量,开始深度优先搜索。
```c
char* findPath(TreeNode* root, int target) {
char path[1000] = "";
preorderTraversal(root, path, target, 0);
// 移除最后的逗号和空格
path[strlen(path) - 2] = '\0'; // 只保留最后一个逗号前的内容
return path;
}
```
阅读全文