先序中序还原二叉树

原创已于 2023-09-26 16:36:59 修改 · 粉丝可见 · 357 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132146177

题目:

样例：

`cobol<br/>6<br/>0 2 1 4 5 3<br/>1 2 4 0 5 3<br/>`

1 4 2 3 5 0

思路：

结合前序的性质特征，中序的性质特征，前序遍历的时候，前面的第一个结点，结合中序数组可以推出，第一个结点是确定结点，而后确定结点在中序数组中，左边的结点数量就是在前序数组该节点往后的相同数量。

在这里唯一的一个重难点还是那个数据范围：

递归左支树操作

// 判断是否有左支树， 结合前序和中序的特征性质，计算相应的数据范围，递归查找结点
if(il < mid) l[root] = biuld(il,il + len - 1,pl + 1,pl + len - 1);

在这里 中序的数据范围，还是那个判断长度

不同点的是 前序数组范围 pl 是  pl + 1

是因为  pl 是我们已经取得到了的结点 root = pre[pl]

随后前序的右边数据范围 就是 加上我们计算到的长度  即 pr = pl + len - 1

递归右支树操作

// 判断是否有右支树， 结合前序和中序的特征性质，计算相应的数据范围，递归查找结点
	if(ir > mid) r[root] = biuld(il + len + 1,ir,pl + len + 1,pr);

在这里，中序的数据范围还是之前那样根据计算的长度推算

不同的是 这里的 pl 为什么不是 pl + len ，是因为 我们 pl 已经取得了 root 

所以我们一定要记得 pl + len + 1，  因为

原来的左支树的前序右边的范围 是  pl + len - 1

所以我们右支树的前序左边的范围是   pl = (pl + len - 1) + 1 = pl + len

但是我们 前序左边的端点已经是 取得了 root = pre[(pl + len)]  所以我们递归的时候记得

pl = (pl + len - 1) + 1 + 1 = pl + len + 1

代码详解如下：

#include <iostream>
#include <unordered_map>
#define umap unordered_map
using namespace std;

const int N = 500;

int n;	// 结点数量

int pre[N];	// 先序数组
int ines[N];	// 中序数组

umap<int,int>l,r,pos;		// l 为左支树的结点 r 为右支树的结点 pos 为 某节点在 中序数组的下标

inline int biuld(int il,int ir,int pl,int pr)
{
	// 根据前序遍历特征性质，取得确定的结点
	int root = pre[pl];

	int mid = pos[root];	// 查询该节点在中序数组的下标

	int len = mid - il;		// 计算 左支树的结点数量

	// 判断是否有左支树， 结合前序和中序的特征性质，计算相应的数据范围，递归查找结点
	if(il < mid) l[root] = biuld(il,il + len - 1,pl + 1,pl + len - 1);

	// 判断是否有右支树， 结合前序和中序的特征性质，计算相应的数据范围，递归查找结点
	if(ir > mid) r[root] = biuld(il + len + 1,ir,pl + len + 1,pr);

	return root;	// 返回取得确定的结点
}

inline void lastorder(int root)
{
	if(l[root]) lastorder(l[root]);

	if(r[root]) lastorder(r[root]);
	
	cout << root;

	if(--n) putchar(' ');	// 控制输出格式

}

int main()
{
	cin >> n;

	for(int i = 0;i < n;++i) cin >> pre[i];

	for(int i = 0;i < n;++i)
	{
		cin >> ines[i];
		pos[ines[i]] = i;
	}

	int root = biuld(0,n - 1,0,n - 1);	// 开始建树，并取得根节点
	
	lastorder(root);	// 后序遍历

	return 0;
}