Problem.png
给出一棵树的中序和后序遍历，问从根到哪个叶结点的权值累加和最大。
已知二叉树的中序和后序，可以构造出这棵二叉树，然后递归深搜这棵树，比较每条路径的累加权值即可。
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
const int maxv = 10000 + 10;
int in_order[maxv], post_order[maxv], lch[maxv] = {0}, rch[maxv] = {0};
int n;
bool read_list(int* a) {
string line;
if (!getline(cin, line)) return false;
stringstream ss(line);
int val;
n = 0;
while (ss >> val) {
a[n] = val;
n++;
}
return true;
}
/**
* in_order[L1...R1]是当前这棵树的中序
* post_order[L2...R2]是当前这棵树的后序
* 算法的主题思想是通过后序的最后一个值找到当前这棵树的根
* 然后在中序中找到根的位置，则左侧为左子树的中序，右侧为右子树的中序
* 再根据左子树的结点个数找出左子树的后序和右子树的后序
* 之后再分别对左子树和右子树进行递归，得到当前根的左孩子和右孩子，完成建树
**/
int build(int L1, int R1, int L2, int R2) {
if (L1 > R1) return 0; // 递归到空树时结束递归
int root = post_order[R2];
int p = L1;
while (in_order[p] != root) {
p++;
}
int lcnt = p - L1; // 左子树的结点个数
// lpost L2, L2 + lcnt - 1
// rpost L2 + lcnt, R2 - 1
lch[root] = build(L1, p - 1, L2, L2 + lcnt - 1);
rch[root] = build(p + 1, R1, L2 + lcnt, R2 - 1);
return root;
}
int best, best_sum;
// 深度优先搜索，不断累加权值
// 因为是递归，所以权值要作为参数
void dfs(int u, int sum) {
sum += u;
if (!lch[u] && !rch[u]) {
if (sum < best_sum || (sum == best_sum && u < best)) {
best = u;
best_sum = sum;
}
}
if (lch[u]) dfs(lch[u], sum); // 有左子树就递归搜索一下左子树
if (rch[u]) dfs(rch[u], sum); // 有右子树就递归搜索一下右子树
}
int main() {
while (read_list(in_order)) {
read_list(post_order);
int root;
root = build(0, n - 1, 0, n - 1);
best_sum = 10000000;
dfs(root, 0);
cout << best << endl;
}
return 0;
}
