实验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++ 的实现，使用了深度优先搜索算法：

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void findPath(TreeNode* root, int sum, vector<int>& path, vector<vector<int>>& res) {
    if (!root) {
        return;
    }
    path.push_back(root->val);
    sum -= root->val;
    if (!root->left && !root->right && sum == 0) {
        res.push_back(path);
    }
    findPath(root->left, sum, path, res);
    findPath(root->right, sum, path, res);
    path.pop_back();
}

vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> res;
    vector<int> path;
    findPath(root, sum, path, res);
    return res;
}

TreeNode* buildTree(vector<vector<int>>& data, int rootIndex) {
    if (rootIndex == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(data[rootIndex][0]);
    root->left = buildTree(data, data[rootIndex][1]);
    root->right = buildTree(data, data[rootIndex][2]);
    return root;
}

int main() {
    int sum, n;
    cin >> sum >> n;
    vector<vector<int>> data(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> data[i][0] >> data[i][1] >> data[i][2];
    }
    TreeNode* root = buildTree(data, 0);
    vector<vector<int>> res = pathSum(root, sum);
    for (auto path : res) {
        for (int i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i != path.size() - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
    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