题解 | #将满二叉树转换为求和树#首先根据前序和中序恢复树结构，然后求和树，最后打印

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int i)
    {
        val=i;
        left=NULL;
        right=NULL;
    }
};
TreeNode* buildTree(vector<int>& pre, vector<int>& in, int pre_s, int pre_e, int in_s, int in_e)
{
    if(pre_s > pre_e)
    {
        return NULL;
    }
    else if(pre_s == pre_e)
    {
        TreeNode* n = new TreeNode(pre[pre_s]);
        return n;
    }
    int inX = in_s;
    for(; inX <= in_e; inX++)
    {
        if(pre[pre_s] == in[inX])
        {
            break;
        }
    }
    int L1 = inX - in_s;
    TreeNode* n = new TreeNode(pre[pre_s]);
    n->left = buildTree(pre,in,pre_s+1,pre_s+L1,in_s,inX-1);
    n->right = buildTree(pre,in,pre_s+L1+1,pre_e,inX+1,in_e);
    return n;
}
int dfs(TreeNode* root)
{
    if(root == NULL) return 0;
    int sum = 0;
    sum += dfs(root->left);
    sum += dfs(root->right);
    int tmp = root->val + sum;
    root->val = sum;
    return tmp;
}
void print(TreeNode* root)
{
    if(root == NULL) return;
    print(root->left);
    cout<<root->val<<" ";
    print(root->right);
}
int main()
{
    vector<int> pre, in;
    int x;
    while(cin>>x)
    {
        //cout << x << endl;
        pre.push_back(x);
        if(cin.get()=='\n')
            break;
    }
    
    int n = pre.size();
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        //cout << x << endl;
        in.push_back(x);
    }
    TreeNode* root = buildTree(pre, in, 0, n-1, 0, n-1);
    //print(root);
    dfs(root);
    print(root);
    
}