7-9 二叉树还原及路径求解 分数 15 作者 张亚军 单位 重庆科技学院 给定二叉搜索树的后序遍历结果，求该树根节点到所有叶子节点的路径及该路径上节点的和，约定树的节点总数不超过1000个。 样例创建的二叉树如图： image.png 输入格式: 二叉搜索树的后序遍历序列。 输出格式: 根节点到所有叶子节点的路径及路径上所有节点的和。结尾无空格。 输入样例: 在这里给出一组输入，如： 15 34 22 10 45 87 76 90 56 40 输出样例: 在这里给出相应的输出。例如： 87: 40->10->22->15 106: 40->10->22->34 141: 40->56->45 349: 40->56->90->76->87写出该代码用c++

以下是求解二叉搜索树后序遍历的根节点到所有叶子节点的路径及路径上所有节点的和的C++代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int postorder[N];
vector<int> path;
int n;

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

TreeNode *buildTree(int left, int right)
{
    if (left > right) return nullptr;

    TreeNode *root = new TreeNode(postorder[right]);

    int k = left;
    while (k < right && postorder[k] < postorder[right]) k++;

    root->left = buildTree(left, k - 1);
    root->right = buildTree(k, right - 1);

    return root;
}

void dfs(TreeNode *root, int sum)
{
    if (!root) return;

    sum += root->val;
    path.push_back(root->val);

    if (!root->left && !root->right)
    {
        cout << sum << ':';
        for (auto x : path) cout << ' ' << x;
        cout << endl;
    }

    dfs(root->left, sum);
    dfs(root->right, sum);

    path.pop_back();
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> postorder[i];

    TreeNode *root = buildTree(0, n - 1);

    dfs(root, 0);

    return 0;
}

思路：根据二叉搜索树的性质，后序遍历序列的最后一个数为根节点，将其分为左子树和右子树，递归构建二叉搜索树。使用深度优先搜索遍历每个节点，记录下路径和路径上的节点值，当遍历到叶子节点时，输出路径和路径上的节点值的和。由于是深度优先搜索，需要记录下每个节点在路径上的位置，因此使用一个vector容器记录当前路径中节点的值。