题解 | #将满二叉树转换为求和树# 依据前序中序结果求和

根据前序遍历，在中序遍历中找到树的根，递归计算左右子树的和

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

void calSum(vector<int>& preorder, vector<int>& inorder, int preStart,
            int preEnd, int inStart, int inEnd, vector<int>& ans) {
    // 已经计算完了
    if (preStart >= preEnd || inStart >= inEnd) {
        return;
    }
    int num, sum = 0; // 记录遍历了几个数以及和
    // 在中序遍历中寻找前序遍历里找到的根
    for (int i = inStart; i <= inEnd; i++) {
        sum += inorder[i]; // 一边找一边统计当前和
        if (inorder[i] == preorder[preStart]) { // 找到了
            sum -= inorder[i];
            num = i - inStart; // 统计一共几个数
        }
    }
    ans[inStart + num] = sum; // 修改对应坐标的值
    // 分别对找到的根的左边和右边进行递归计算
    calSum(preorder, inorder, preStart + 1, preStart + num, inStart,
           inStart + num - 1, ans);
    calSum(preorder, inorder, preStart + num + 1, preEnd, inStart + num + 1,
           inEnd, ans);
}

int main() {
    int x;
    vector<int> preorder;
    while (cin >> x) {
        preorder.push_back(x);
        if (cin.get() == '\n') {
            break;
        }
    }
    int n = preorder.size();
    vector<int> inorder(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
    }
    vector<int> ans(n, 0);
    calSum(preorder, inorder, 0, n - 1, 0, n - 1, ans);
    for (const auto& x : ans) {
        cout << x << " ";
    }
    return 0;
}

时间复杂度：在最坏情况下，每次递归调用calSum函数都需要遍历中序遍历序列找到根节点，时间复杂度为O(n^2)，其中n为节点数。整体时间复杂度为O(n^2)。

空间复杂度：除了输入数据占用的空间外，递归调用calSum函数时会消耗栈空间，最大递归深度为树的高度，即O(n)。同时，结果向量和其他辅助变量所占空间也为O(n)。整体空间复杂度为O(n)。