后序中序还原二叉树

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

题目：

样例：

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

0 2 1 4 5 3

思路：

在这里，要懂得后序遍历以及中序遍历的性质特征，也就是中序的左支树节点数量必定是后序数组的前面相同数量上的各个节点。中序的右支树是后序数组随后的剩余的各个结点

这里唯一的难点，就是如何确定建树的范围，特别是右支树

左支树很简单，因为就是前几个

所以

 len = mid - il


l[root] = biuld(il,il + len - 1,ll,ll + len - 1);

 ir = il + len - 1

 lr = ll + len - 1

而到了右支树

r[root] = biuld(il + len + 1,ir,ll + len,lr - 1);

 这里的  il = il + len + 1  是因为 我们 中序中 mid 以及取出来了 
 所以  il = il + (len - 1) + 2 = il + len + 1

 而后序数组中  

 ll = ll + len    是因为 它不像 中序数组是已经取出来了  所以我们还是要取到该点

 所以 ll = ll + (len - 1) + 1

详解代码如下：

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

const int N = 500;

int n;	// 结点数量

int last[N];	// 后序数组
int ines[N];	// 中序数组

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

inline int biuld(int il,int ir,int ll,int lr)
{
	int root = last[lr];	// 根据 后序遍历的性质特征 取得结点

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

	int len = mid - il;		// 取得 左支树的 结点数量，也是需要递归查找 后序数组 的长度
	
	// cout << mid << endl;

	if(il < mid)	// 如果 中序数组的 左端点 比 该节点 在 中序数组的下标还要小，说明还可以进行查找
	{
		// 结合 中序遍历 和 后序遍历 的性质特征 ，推出 该结点的 左支树，左节点是多少
		l[root] = biuld(il,il + len - 1,ll,ll + len - 1);
	}

	if(ir > mid)	// 如果 中序数组的 右端点 比 该节点 在 中序数组的下标还要大，说明还可以进行查找
	{
		// 结合 中序遍历 和 后序遍历 的性质特征 ，推出 该结点的 右支树，右节点是多少
		r[root] = biuld(il + len + 1,ir,ll + len,lr - 1);
	}

	return root;	// 返回所取得的节点
}

inline void preorder(int root)	// 前序遍历
{
	cout << root;
	if(--n) putchar(' ');	// 控制输出格式
	if(l[root]) preorder(l[root]);
	if(r[root]) preorder(r[root]);	
}

int main()
{
	cin >> n;

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

	for(int i = 0;i < n;++i)
	{
		cin >> ines[i];
		pos[ines[i]] = i;	// 存储 中序数组 的各个节点的下标
	}

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

	preorder(root);

	return 0;
}