重建二叉树

2017-12-27

问题描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8,6}，则重建出图所示的二叉树并输出它的头结点。

分析
刚看到问题的时候感觉比较棘手，之前写过一个根据前序和中序输出后序的第一个元素的题目，感觉跟这个是有些相似。后来认真分析问题后，觉得第一个解决的是如何创建一个二叉树，这在那篇数据结构和算法中写了一个是通过中序序列来创建的，那个创建要求是把一个树按照扩展的前序序列输入，一个节点没有左右子树的话就用特殊字符代替。比如这棵树的扩展的前序序列为：124#7###35##68###，之后通过一个递归算法来创建二叉树。之后我就在想用这种方法来重建二叉树，我只要通过前序和中序序列找到扩展的前序序列即可。
接着就来分析如何通过中序和后序来构建扩展的前序序列。其实在分析这个问题的时候，你可以用大脑，通过前序和中序来把这个二叉树画出来，步骤是这样的，首先在前序中找到第一个元素，那么这个元素一定是这个树的根，之后去中序遍历中找到这个节点，那么在中序序列中，这个节点的左边就是左子树，这个节点的右边就是右子树。之后你需要在前序序列中找到这两个子树。最后就是重复上面的过程就可以了，如果没有了子树就是叶子节点了。
算法的思路也是根据上面的想法写出来的，上面的过程明显是一个递归的过程。而关键是找到根的位置，以及前序和中序中子树的范围。
C语言实现

#include<stdio.h>
#include<stdlib.h>
#define MAX 65536
int pre[MAX];
int in[MAX];
int expre[MAX];
int plen, exlen = 0;
int low = 0;
typedef struct t
{
	int key;
	struct t *right;
	struct t *left;
}T;
void creat(T **t)
{
	int k = expre[low++];
	if(k == -1)
		*t = NULL;
	else
	{
		*t = (T*)malloc(sizeof(T));
		(*t)->key = k;
		creat(&(*t)->left);
		creat(&(*t)->right);
	}
}
void preorder(T *root)
{
	if(root != NULL)
	{
		printf("%d ", root->key);
		preorder(root->left);
		preorder(root->right);
	}
}
void input()
{
	scanf("%d", &plen);
	int i = 1;
	while(i <= plen)
	{
		scanf("%d", &pre[i]);
		i++;
	}
	i = 1;
	while(i <= plen)
	{
		scanf("%d", &in[i]);
		i++;
	}
}
int seek(int low, int high, int root)
{
	while(low <= high)
	{
		if(root == in[low])
			return low;
		low++;
	}
	return -1;
}
void calc(int plow, int phigh, int inlow, int inhigh)
{
	expre[exlen++] = pre[plow];
	int index = seek(inlow, inhigh, pre[plow]);
	if(inlow < index)
		calc(plow + 1, plow + (index - inlow), inlow, index - 1);
	else
		expre[exlen++] = -1;
	
	if(inhigh > index)
		calc(plow + (index - inlow) + 1, plow + (index - inlow) * 2, index + 1, inhigh);
	else
		expre[exlen++] = -1;
}
int main()
{
	freopen("v7.txt", "r", stdin);
	input();
	calc(1, plen, 1, plen);
	T *t = NULL;
	creat(&t);
	preorder(t);
	puts("");
	return 0;
}

这次没写测试用例，人眼把剑指offer的测试用例都测试了一下，都通过了。其实细节要考虑的是左子树和右子树的范围问题，这一点我写的比较粗糙。也就是代码83到91这之间的内容。