题目：二叉树路径查找

给定一棵二叉树(结构如下)，其中每个节点值为整数。给定一个值 K，求所有满足如下条件的路径并将路径 上节点的值打印出来： 1、路径方向必须向下，即只能从父节点指向子节点 2、路径并不是必须从根节点开始或在叶节点结束。即树上任意节点开始向下走到任意节点的路径都 允许。 3、路径上的节点得分之和等于给定值 K。节点得分=节点值+节点所在层(根节点为 0，之后每层+1)。

参考答案

#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;
    }
    


}