# 参考答案

```#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

// 树的结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//输出路径
void printPath(const vector<int>& path)
{
for (int i = 0; i < path.size(); i++) {
if (i != 0) cout << " ";
cout << path[i];
}
cout << endl;
}

//根据序列构造树
TreeNode* buildTree(const vector<string>& nodes) {
if (nodes.empty()) return nullptr;

TreeNode* root = new TreeNode(stoi(nodes[0]));
queue<TreeNode*> q;
q.push(root);

int i = 1;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();

if (i < nodes.size() && nodes[i] != "null") {
node->left = new TreeNode(stoi(nodes[i]));
q.push(node->left);
}
++i;

if (i < nodes.size() && nodes[i] != "null") {
node->right = new TreeNode(stoi(nodes[i]));
q.push(node->right);
}
++i;
}

return root;
}

//从指定节点开始寻找路径，不一定是根节点
void findPath(TreeNode* node, int restSum , int depth, vector<int>& path, vector<vector<int>>& res) {
if (!node) return;

int new_sum = restSum - node->val - depth;
path.push_back(node->val);

// debug: 输出剩余的路径数目
//cout << new_sum << "\t";
//printPath(path);

if (new_sum == 0) {
res.push_back(path);
}

findPath(node->left, new_sum, depth + 1, path, res);
findPath(node->right, new_sum, depth + 1, path, res);

path.pop_back();
}

//递归从每个节点开始找
void findPathCurNode(TreeNode* root, int sum, vector<vector<int>>& res, int depth) {
if (!root) return;

vector<int> path;
findPath(root, sum, depth, path, res);

findPathCurNode(root->left, sum, res, depth+1);
findPathCurNode(root->right, sum, res, depth + 1);
}

int main() {
while (true) {
cout << "input K and Tree:" << endl;

int K; cin >> K;
cin.ignore();

string line; getline(cin, line);
stringstream ss(line);

vector<string> nodes;
string node;
while (ss >> node) nodes.push_back(node);

TreeNode* root = buildTree(nodes);

vector<vector<int>> res;
findPathCurNode(root, K, res, 0);

cout << endl << "output:" << endl;
for (const auto& path : res) {
printPath(path);
}
cout << endl;
}

}
```

2 回复

1 回复

9 12 评论