Uva548 Tree(十多次RE自闭)

题目描述

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

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

Sample Output

1
3
255

正解：

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e4+10;
int mseq[N],pseq[N];
int e[N],l[N],r[N];
int h,idx;

void init(){
	h = -1;
	idx = 0;
}

int getNum(string &s,int num[]){
	stringstream ss(s);
	int i=0,n;
	while(ss>>n){
		num[i++] = n;
	}
	return i;
}

void buildTree(int L1,int R1,int L2,int R2,int &root){
	if(L1>R1)
		return ;
	root = idx++;
	e[root] = pseq[R2];
	l[root] = -1;
	r[root] = -1;
	int i=L1;
	while(mseq[i]!=e[root])
		i++;
	buildTree(L1,i-1,L2,L2+(i-L1)-1,l[root]);
	buildTree(i+1,R1,L2+(i-L1),R2-1,r[root]);
}

int minn,minx;
void dfs(int now,int sum)
{
	sum += e[now];
	if(l[now] == -1 && r[now] == -1)
	{
		if(sum<minn || (sum==minn&&e[now]<minx))
		{
			minx=e[now];
			minn=sum;
		}
	}
	if(~l[now])
		dfs(l[now],sum);
	if(~r[now])
		dfs(r[now],sum);
}

int main()
{
	string s1,s2;
	while(getline(cin,s1) && getline(cin,s2)){
		int n1 = getNum(s1,mseq);
		int n2 = getNum(s2,pseq);
		init();
		buildTree(0,n1-1,0,n2-1,h);
		minn = INF;
		dfs(h,0);
		cout<<minx<<endl;
	}
	return 0;
}

吐槽总结：

初看这道题不是很难，不过用到了不少东西，不过让我气愤的还是不到几行的一个函数代码：

int init(){//应该是void,怪我了
	h = -1;
	idx = 0;
}

编译器没给我报错，我就兴冲冲地交到VJ Uva上，然后就给我RE，查了一遍，没发现毛病，我就删了几部分代码继续查；其他三个函数不是删了就是直接return；就剩这里了，查了一遍，这里没数组怎么可能越界或除零呢，我就找了个和我思路一样的题解先教一遍（我想看看OJ是不是出毛病了），结果当然是过了然后我就改两个代码，两串代码越来越像，网上的还是一直AC，我的一直RE经历20多次的失败终于找到了 /(ㄒoㄒ)/~~

附图片：