题意
输入一个二叉树的中序和后序遍历,请你输出一个叶子节点,该叶子节点到根的数值总和最小,且这个叶子是编号最小的那个。 输入: 您的程序将从输入文件中读取两行(直到文件结尾)。第一行是树的中序遍历值序列,第二行是树的后序遍历值序列。所有值将不同,大于零且小于或等于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;
}