C++ 利用 中序 与 后序，求出 前序

C++ 利用 中序 与 后序，求出 前序

• 1、题目描述
• 2、解题
• • 2.1 思路
  • 2.2 代码

1、题目描述

给出一个二叉树的中序与后序遍历结果，求出其前序遍历结果。如
输入：“BADC”，“BDCA”
输出：“ABCD”

2、解题 2.1 思路

思路之一，即通过中序与后序的遍历结果，先求出原二叉树的排列，然后再对二叉树作前序遍历。
思路之二，直接根据中序与后序结果，求出前序遍历结果。
下面的实现是基于第二个思路！

2.2 代码

int getPos(char c, string inStr)
{
	int pos;
	for (pos = 0; pos < inStr.size(); pos++)
	{
		if (inStr[pos] == c)
			break;
	}
	return pos;
}
void func(int inlidx, int inridx, int postlidx, int postridx, string inStr, string postStr, string& ans)
{
	int pos = getPos(postStr[postridx], inStr);
	ans.push_back(postStr[postridx]);
	int tmpl = pos - inlidx;
	int tmpr = inridx - pos;
	if (pos > inlidx)
		func(inlidx, pos - 1, postlidx, postridx - tmpr - 1, inStr, postStr, ans);
	if (pos < inridx)
		func(pos + 1, inridx, postlidx + tmpl, postridx - 1, inStr, postStr, ans);
}
string preorderString(string inorderString, string postorderString)
{
	int sz = inorderString.size();
	string ans;
	func(0, sz - 1, 0, sz - 1, inorderString, postorderString, ans);
	return ans;
}