用C语言实现在在二叉树中找出和为某一值的所有路径
时间: 2024-05-10 20:17:47 浏览: 90
以下是使用C语言实现在二叉树中找出和为某一值的所有路径的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void findPath(TreeNode* root, int sum, int* path, int depth) {
if (root == NULL) {
return;
}
path[depth] = root->val;
int i, curSum = 0;
for (i = depth; i >= 0; --i) {
curSum += path[i];
if (curSum == sum) {
int j;
for (j = i; j < depth; ++j) {
printf("%d->", path[j]);
}
printf("%d\n", path[depth]);
}
}
findPath(root->left, sum, path, depth + 1);
findPath(root->right, sum, path, depth + 1);
}
int main() {
// 构造二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 10;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 5;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 12;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 7;
// 在二叉树中查找和为22的路径
int path[100];
findPath(root, 22, path, 0);
// 释放二叉树空间
free(root->left->left);
free(root->left->right);
free(root->left);
free(root->right);
free(root);
return 0;
}
```
该示例代码中,我们先构造了一棵二叉树,并在其中查找和为22的路径。在查找路径的过程中,我们使用了深度优先遍历的方法,通过一个数组来保存当前已经走过的路径,每次遍历到一个节点,则将该节点的值加入路径中。在加入值之后,我们检查路径中是否存在和为目标值的子路径,如果存在,则输出该路径。最后,我们递归遍历该节点的左子树和右子树,以便查找所有可能的路径。
需要注意的是,该示例代码中并未考虑二叉树中存在负数的情况,如有需要,可以根据实际情况进行修改。
阅读全文