题意
输入一个二叉树的中序和后序遍历，请你输出一个叶子节点，该叶子节点到根的数值总和最小，且这个叶子是编号最小的那个。 输入： 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同，大于零且小于或等于10000.二叉树的节1<=N<=10000。 输出： 对于每个树描述，您应该输出最小值路径的叶节点的值。存在多路径最小的情况下，您应该选择终端叶子节点上具有最小值的那条路径，且输出那个最小值的终端叶子。
输入
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
思路:本题先通过中序和后序构建二叉树,然后先序获得路径长度.
大概需要三个函数:readline(int *arr):读取中序和后序序列.
createTree(int l1,int l2,int len):建立二叉树
findmin(int v,int sum) :寻找最小路径和最小编号节点.
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 10010; int postorder[maxn],inorder[maxn],lch[maxn],rch[maxn],n,x; int minsum,minv; string str,str2; bool readline(int *arr){//一次读入一行 //getline(cin,str); if(!getline(cin,str)){ return false; } stringstream s(str); n = 0,x; while(s>>x){//stringstream 可以进行字符串和整形的相互转化. arr[n++] = x; } return true; } int createTree(int l1,int l2,int len){//中序后序创建二叉树. if(len<=0){//递归结束 叶子节点其左右子树的值为0 return 0; } int root = postorder[l2+len-1];// int len2=0; while(inorder[l1+len2]!=root){//len2根节点左子树的长度. len2++; } lch[root]=createTree(l1,l2,len2); rch[root] = createTree(l1+len2+1,l2+len2,len-len2-1); //rch[root] = createTree(l1+len2+1,l2+len2+1,len-len2-1);因为是后序,根节点在最后所以,右子树处理不应该再+1 return root; } void findmin(int v,int sum){//寻找权路径之和最小的叶子 如果有多个,则返回叶子结点最小的那个. sum += v; if(lch[v]==0&&rch[v]==0){//递归结束 if(sum<minsum ||(sum == minsum &&v < minv )){//满足题意进行交换 minsum = sum; minv = v; } return; } if(lch[v] > 0){ findmin(lch[v],sum); } if(rch[v]>0){ findmin(rch[v],sum); } } int main() { while(readline(inorder)){ readline(postorder); //cout<<"hahah"<<endl; minsum=0xfffffff,minv=0xfffffff; createTree(0,0,n); //cout<<"二叉树构建完成"<<endl; findmin(postorder[n-1],0); cout<<minv<<endl; } return 0; }
