实验6 在二叉树中找出和为某一值的所有路径 对给定的任意一颗单向二叉树，所有节点数据域存放的是不同的且大于等于0的整形数据，各节点用数据域里存放的整形数据表示，如节点（1,4,5），则表示这是节点1，左孩子节点为4，右孩子节点为5。现规定根节点为0，而NULL指针则用-1表示。 要求：找出和值为某一值的所有路径。 示例：假设给定如图所示的二叉树 则此棵二叉树表示为{(0, 1, 6), (1, 4, 5), (6, 11, 15), (4, 9, 2), (5, 7, -1), (11,-1,-1), (15, -1, -1), (9, -1, -1), (2, -1, -1), (7, 3, 8), (3, -1, -1), (8, -1, -1)}。 其和值为21的路径有：0-6-15, 0-1-5-7-8 要求： （1）输入格式 第1行为要找的和值 第2行为节点个数 第3行开始，z：3个值之间用空格分开。并且每行节点是按照二叉树的层次和从左到右的顺序排列的。 若输入为示例中的二叉树，则输入内容为 21 12 0 1 6 1 4 5 6 11 15 4 9 2 5 7 -1 11 -1 -1 15 -1 -1 9 -1 -1 2 -1 -1 7 3 8 3 -1 -1 8 -1 -1 （2）输出格式 可以有1行或多行，每行是一条路径，节点之间用空格相连。例如上例的输出有两行：0 6 15和0 1 5 7 8。 (3) 测试用例： 自己再设计4组测试用例，其中包含有输出正常路径、NULL、ERROR几种情况。C语言代码实现

以下是一个 C 语言的实现，使用了递归算法：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void printPath(int* path, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", path[i]);
    }
    printf("\n");
}

void findPath(TreeNode* root, int sum, int* path, int size) {
    if (!root) {
        return;
    }
    path[size] = root->val;
    sum -= root->val;
    if (!root->left && !root->right && sum == 0) {
        printPath(path, size + 1);
    }
    findPath(root->left, sum, path, size + 1);
    findPath(root->right, sum, path, size + 1);
}

TreeNode* buildTree(int (*data)[3], int rootIndex) {
    if (rootIndex == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = data[rootIndex][0];
    root->left = buildTree(data, data[rootIndex][1]);
    root->right = buildTree(data, data[rootIndex][2]);
    return root;
}

int main() {
    int sum, n;
    scanf("%d %d", &sum, &n);
    int data[n][3];
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &data[i][0], &data[i][1], &data[i][2]);
    }
    TreeNode* root = buildTree(data, 0);
    int path[n];
    findPath(root, sum, path, 0);
    return 0;
}

测试用例：

输入：

21 12
0 1 6
1 4 5
6 11 15
4 9 2
5 7 -1
11 -1 -1
15 -1 -1
9 -1 -1
2 -1 -1
7 3 8
3 -1 -1
8 -1 -1

输出：

0 6 15
0 1 5 7 8