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

C++ 利用 中序 与 后序,求出 前序,第1张

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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/2991811.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

随机推荐

  • 干粉灭火器有效期几年 年检

    干粉灭火器一年检查一次,有效期分为筒体有效期和灭火剂有效期。1、灭火器筒体:按照国家相关规定,干粉灭火器的筒体强制报废年限是10年。2、干粉灭火剂:按照国家建筑灭火相关规定干粉灭火器一年检查一次,有效

    2022-10-01
    0 0 0
  • 信阳毛尖属于什么茶

    信阳毛尖属于绿茶,是中国十大名茶之一,河南省著名的特产,信阳毛尖历史悠久,在唐朝时期被列为贡品。信阳毛尖具有细圆、光直、香高味浓等多种特点,适当的饮用此茶,可有清心明目、提信阳毛尖属于绿茶,是中国十大

    2022-10-01
    0 0 0
  • 素什锦的原料有哪些

    素什锦原料有黄花菜、香菇、黑木耳、油面筋、素肠、毛豆、鸡毛菜、熟笋肉、五香豆腐干、边尖笋、白糖、酱油、精盐、味精、植物油、素鲜汤等。什锦菜是南京特有的素菜,属金陵素什锦原料有黄花菜、香菇、黑木耳、油面

    2022-10-01
    0 0 0
  • 学弈翻译

    弈秋是全国最擅长下棋的人。让弈秋教导两人下棋,其中一人聚精会神,只听弈秋的教诲。另一个人虽然听弈秋教导,却一心想着将有大雁飞来,想用弓箭射它。他们虽然一起学习下棋,但后者弈秋是全国最擅长下棋的人。让弈

  • 金龟子会飞吗

    金龟子会飞。金龟子是鞘翅目金龟总科的通称,属动物界、节肢动物门、昆虫纲,分为大黑鳃金龟、东方金龟、小青花金龟。金龟子的幼虫(蛴螬)是主要地下害虫之一,危害严重,常将植物的幼金龟子会飞。金龟子是鞘翅目金

    2022-10-01
    0 0 0
  • 中外文化交流的例子

    1、张骞出使西域:汉武帝招募使者,派他们到月氏氏族去攻打匈奴。张骞招使者,出使长安。他往西到大源、经过康州、到了大月,然后到了大察。他待了一年多才回来。2、郑和下西洋:郑和1、张骞出使西域:汉武帝招募

    2022-10-01
    0 0 0
  • 小行星是怎样命名的

    发现了新小行星;小行星获得年份、字母和数字组成的&ldquo;暂定编号&rdquo;;如果小行星能再被观测到至少两次,使得轨道可以被准确测定;轨道被测定的足够精确之后,小行星获得一个正发现了新小行星;

    2022-10-01
    0 0 0
  • 2020年公务员考试成绩公布时间 2020年公务员考试成绩什么时候公布

    2020年公务员考试成绩公布时间是2020年1月上旬。2020国家公务员考试已于2019年11月24日结束,根据2020国考公告,报考者可于2020年1月登录考录专题网站查询笔试成绩和最低合格分202

    2022-10-01
    0 0 0
  • 烟雨江湖温书房怎么进

    烟雨江湖温书房怎么进,来看吧。温家要搜书房的话需要闯进去才能搜。子时先去客厅偷钥匙,然后去书房。不过,你打不过老温的话,也打不过戚夫人。戚夫人水平跟老温差不多,不如硬闯算烟雨江湖温书房怎么进,来看吧。

    2022-10-01
    0 0 0

发表评论

登录后才能评论

评论列表(0条)

保存