一、题意

每组数据一棵树。
给出树的中序遍历和后序遍历，求这棵树的叶子节点中，到根节点的权值和最小的那个结点的权值。

二、解析

由中序遍历和后续遍历就可以恢复出完整的树。
然后再对树做dfs求出答案。

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
const int maxn = 10000 + 5, INF = 1 << 30;
struct node {
    int val;
    node *l, *r;
    node(node* l, node* r) : l(l), r(r) {}
};
int mid[maxn], post[maxn];
int min_sum, ans;

void buildTree(node* & root, int* mid, int* post, int n) {
    if(n == 0) return;
    if(root == nullptr) root = new node(nullptr, nullptr);
    if(n == 1) {
        root->val = mid[0];
        return;
    }
    int i = 0;
    for(; i < n && mid[i] != post[n - 1]; i ++);
    root->val = mid[i];
    buildTree(root->l, mid, post, i);
    buildTree(root->r, mid + i + 1, post + i, n - 1 - i);
}

void dfs(node* root, int sum) {
    if(root == nullptr) return;
    sum += root->val;
    if(root->l == nullptr && root->r == nullptr) {
        if(sum < min_sum || sum == min_sum && root->val < ans) min_sum = sum, ans = root->val;
        return;
    }
    dfs(root->l, sum);
    dfs(root->r, sum);
}

int main() {
    string str1, str2;
    while(getline(cin, str1)) {
        getline(cin, str2);
        min_sum = INF, ans = INF;
        stringstream ss1(str1), ss2(str2);
        int num, i = 0, j = 0;
        while(ss1 >> num) mid[i ++] = num;
        while(ss2 >> num) post[j ++] = num;
        node* root = nullptr;
        buildTree(root, mid, post, i);
        dfs(root, 0);
        cout << ans << endl;
    }
}

四、归纳

  • 注意1：不要用 &vec[0] 的方式企图获取指针，这样会造成段错误
  • 注意2：递归式一定要想全递归出口，不要遗漏，特别是0值或null值的判断