二叉树：已知前序与后序建树

已知前序与中序、后序与中序建树是常遇到的算法问题。若已知前序序列与后序序列，要求输出满足条件的树的个数或者输出所有可能的树的中序序列，该怎么解决？下面我们一步步讨论这个问题。

首先，已知一个树的结点数n，共有多少种树形？（或者，已知一颗树的先序/中序/后序序列，共有多少种树形？）
答案是$C_m^n/(n+1)$种。点这里了解一下卡特兰数
那么，这里就有一种暴力解法，就是建立所有可能的树形，将先序序列填入某一树形，比较此树的后序序列是否与给定后序序列相同，若相同则找到一个解，若不相同，则填入下一个树形，直到填完所有可能树形。当树的结点为10时，那么总共有16796种树形，因此这种暴力解法时间复杂度相当高。
那么我们换一种思考方式，我们先来看看先序与后序序列的排布规律。以下面这棵树来举例：

其先序序列为： 1 2 3 4 6 7 5
后序序列为：2 6 7 4 5 3 1

首先我们要知道：

先序序列遍历顺序是：根结点-左子树-右子树

后序序列遍历顺序是：左子树-右子树-根结点

很明显，我们可以看出结点在先、后序列中的排布有以下这些特征：
【1】、在先序序列中，根结点在子树中的结点前面，在后序序列中，根结点在子树中的结点后面。
【2】、以任一节点为根结点时，其子树在后序序列中排布都是先左子树后右子树，而根结点排在最后。
那么，反过来思考，已知这个先序与后序序列所确定的树是唯一的吗？进一步推广：怎么通过先序与后序序列判断是否存在唯一的树呢？

现在，我们来一步步分析已知先序与后序的建树过程：

①、根据特征【1】可知：根结点为先序序列第一个节点以及后序序列最后一个结点，因此根结点为1。

②、先序序列中第二个结点为2，其在后序序列中的位置是第一个，那么根据特征【2】我们可以知道结点2是没有子树的，而且结点2要么在根结点的左子树，要么在右子树。假设结点2在右子树，那么由特征【2】可知根结点1没有左子树，而且先序序列中结点2后面的结点全部为结点2的子树上的结点。再看后序序列，由特征【2】可知，结点2后面的结点不可能是其子树上的结点。因此，假设显然与已知矛盾。这样，我们又知道结点2是结点1的左孩子，且结点2没有子结点。

③、先序序列第三个位置上的结点为3，该结点在后序序列中排倒数第二个。由②可知，结点3必然是根结点1的右孩子。

④、先序序列第四个位置上的结点为4，该结点在后序序列中排第四个。因为结点4在先序序列中排在结点3后面，又因为结点3是根结点1的右孩子，所以结点4只可能在结点3的子树上。结点3的子树可能出现的情况是：只有左子树，只有右子树，左右子树都有。因为在后序序列中，结点4左边是结点6、7，右边是结点5。所以结点5并不在结点4的子树上，所以结点3既存在左子树又存在右子树。这样的话，出现在结点3后面的第一个结点必然为结点3的左子树，所以结点4是结点3的左孩子，且由特征【2】可知，结点6、7在以结点4为根结点的子树，上，结点5是结点3的右孩子。

⑤再看结点6，其在先序序列中排在第五位，在后序序列中排在第二位。同理，结点4的子树可能出现的情况是：只有左子树，只有右子树，左右子树都有。假设，接4只有左子树，那么结点6必然为结点4的左孩子，结点7必然为结点6的孩子，而根据特征【2】，因为结点7在后序序列中排在结点6后面，因此结论与假设矛盾。同样可以排除只有右子树的情况。那么我们可以得到：结点4既有左子树又有右子树，由特征【2】可知结点6为结点4的左孩子，结点7为结点4的右孩子。

至此，我们已经分析了一遍如何通过二叉树的先、后序序列建立一个二叉树，但是由这个例子中的先、后序序列确定的树是唯一的。现在我们再从分析过程中提炼一些排列特征出来：
【3】在后序序列中，若一个结点的左侧没有在先序序列中排在该结点后面的结点（如结点2，在先序序列中排在其后面的结点有3 4 6 7 5 但在后序序列中结点2前面没有这些结点），那么这个结点必然没有孩子。

再来看看这样一个例子：

先序序列：1 2 3 4
后序序列：2 4 3 1

我们再来建立一棵满足上述条件的树：
通过上一个例子，我们可以很快得到结点1为根结点，结点2为结点1的左孩子，结点3为结点1的右孩子，但是我们发现：结点4既可以是结点3的左孩子，又可以是右孩子。我们可以看到，之所以结点4的位置无法确定，是因为结点3只有一个子节点，而这个子节点既可以是左孩子，又可以是右孩子。
至此，我们可以得到确定一个结点位置是否唯一的方法：检测其父节点是否只有一个子节点。
因此可以得到特征：
【4】在先序序列中，若根结点的下一个位置上的结点在后序序列中的位置在后序序列根结点的左边一个位置，那么说明树不唯一，树的个数与出现这种情况相关(2^n)。

为了更好的解释特征【4】，我们可以看这样一个例子：

先序序列：1 2 4 5 6 3
后序序列：4 2 3 6 5 1

当我们对这棵树进行划分时，我们可以得到以结点1为根结点时的左右子树：
左子树（先序/后序）：2 4 / 4 2
右子树（先序/后序）：5 6 3 / 3 6 5

我们看这里的右子树的先序序列与后序序列：当结点5作为结点1的右子树的根结点时，在先序序列中结点5下一个位置的结点6在后序序列中位于后序序列中结点5的左边一个位置，因此说明对于结点5而言，树不唯一。

Some practices for you

利用上面所阐述的方法，我们来计算一下下面这些例子可以确定多少种树：

先序序列：1 2 3 4 5 6
后序序列：3 2 5 6 4 1

先序序列：1 2 4 5 6 3
后序序列：4 2 3 6 5 1

先序序列：1 3 4 5 6 2 7
后序序列：5 4 3 2 7 6 1

答案分别为：2，8，1
树形可以为：

Code

c/c++代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 50;int n;
int pre[maxn],post[maxn],pos[maxn];
bool isunique = true;// 判断是否唯一struct node{int data;node *lchild,*rchild;
};void inorder(node *&root,int prel,int prer,int postl,int postr){if(prel == prer){root = new node;root->data = pre[prel];root->lchild = root->rchild = NULL;return;}else if(prel>prer || postl>postr){return;}if(pre[prel] == post[postr]){root = new node;root->data = pre[prel];root->lchild = root->rchild = NULL;int numchild = postr-pos[pre[prel+1]];if(numchild == 1){isunique = false;}int postloc = pos[pre[prel+1]];int numleft = postloc-postl; inorder(root->lchild,prel+1,prel+numleft+1,postl,postl+numleft);inorder(root->rchild,prel+numleft+2,prer,postl+numleft+1,postr-1);}
}int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&pre[i]);}for(int i=0;i<n;i++){scanf("%d",&post[i]);pos[post[i]] = i;}node *root = NULL;inorder(root,0,n-1,0,n-1);return 0;
}

说明一下：
1、调用inorder()函数得到root便获取到了建成的树，其中位置不确定的结点都被认为是左结点。
2、若想统计不同的树形个数，可以对以下语句进行修改：

将:
bool isunique = true;
...
if(numchild == 1){isunique = false;
}
改为:
int isunique = 0;
...
if(numchild == 1){isunique++;
}
此时树形个数为2^isunique个,想一想为什么是2为底数？

PAT上有类似的题目:
PAT Advancedlevel 1119 Pre- and Post-order Traversals
本题也可以不建树直接得到中序遍历，这里就不再讨论，想继续了解的朋友请狠狠的点击这里，查看柳神的方法

感觉推导过程写的不清楚的请留言，我会不定期来修改。