uva548Tree

题目大意：

       给你一棵二叉树的中序遍历和后序遍历，让你找从根到叶子结点的路径最短的叶子结点，如果有多个路径符合，就选择叶子结点最小的结点。

然而题意看错两次。。。。。。第一次以为只找值最小的叶子结点，第二次以为选择第一次出现的最短路径。。。。。。注意以后看题时不要通过input，output来推测题意。而是在把前言理解的基础上，再看题。题目错了就呵呵了。

思路：

      因为题目只要求解出结果，便不需要实际建树，只是模拟建树即可，用两个变量p1,p2限制后序遍历的树的左右界限，in1，in2来限制中序遍历树的左右界限，还有一个变量path保存路过结点的值。将一个大树劈成两个左右子树（更新path），，，，，，一直给我劈，，，，，，直到只剩一个枝条没法劈，才将它与最短路径比较。

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<sstream>

using namespace std;

const int inf = 0x3f3f3f3f;
int inorder[10004], n, ans, minn;
int postorder[10004];

void build(int pl, int pr, int inl, int inr, int path)
{
	if (pl > pr)
		return;
	if (pl == pr)
	{
		if (path + postorder[pl] <= minn)
		{
			if (path + postorder[pl] == minn)
			{
				ans = ans < postorder[pl] ? ans : postorder[pl];
			}
			else
			{
			    minn = path + postorder[pl];
		    	ans = postorder[pl];
			}
		}
		return;
	}
	int fir = postorder[pr];
	for (int i = inl; i <= inr; ++i)
	{
		if (inorder[i] == fir)
		{
				build(pl, pl + i - inl - 1, inl, i - 1, path + inorder[i]);
				build(pr - (inr - i), pr - 1, i + 1, inr, path + inorder[i]);
				break;
		}
	}
}

int main()
{
	memset(inorder, 0, sizeof(inorder));
	memset(postorder, 0, sizeof(postorder));
	string s;
	while (getline(cin, s))
	{
		if (s.size() == 0)
			break;
		stringstream st(s);
		n = -1;
		while (st >> inorder[++n])
			;
		getline(cin, s);
		stringstream str(s);
		int cn = 0;
		ans = inf;
		minn = inf;
		while (str >> postorder[cn++])
			;
		build(0, n - 1, 0, n - 1, 0);
		cout << ans << endl;
	}
}

uva548Tree

原文：http://blog.csdn.net/qq_33665647/article/details/51331840