题目描述

PDF

输入格式

输出格式

题意翻译

输入一个二叉树的中序和后序遍历，请你输出一个叶子节点，该叶子节点到根的数值总和最小，且这个叶子是编号最小的那个。 输入： 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同，大于零且小于或等于10000.二叉树的节1<=N<=10000。 输出： 对于每个树描述，您应该输出最小值路径的叶节点的值。存在多路径最小的情况下，您应该选择终端叶子节点上具有最小值的那条路径，且输出那个最小值的终端叶子。

Translated by @凉凉

输入输出样例

输入 

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

输出 

1
3
255

代码

#include<iostream>
#include<string>
#include<sstream>using namespace std;const int N = 1e4 + 10;//因为各个节点的权值各不相同且都是正整数，直接用权值作为节点编号 
int in_order[N], post_order[N], lch[N], rch[N];//中序 后序 左右儿子int n;//节点数 bool read(int *a)//读入数据 
{string line;if(!getline(cin, line)) return false;stringstream ss(line);n = 0;int x;while(ss >> x)a[n ++] = x;return n > 0;
}//把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 cnt = p - l1;//左子树节点个数lch[root] = build(l1, p - 1, l2, l2 + cnt - 1);rch[root] = build(p + 1, r1, l2 + cnt, 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(in_order)){read(post_order);build(0, n -1, 0, n - 1);best_sum = 2e9;dfs(post_order[n - 1], 0);cout << best << endl;}return 0;
}