事实上，中序遍历序列是必需要有的，前序序列和后序序列有一个就能够推出整棵二叉树了。ios
咱们以 利用中序遍历序列 和 后序遍历序列 获得 整棵二叉树 为例数组
如何作 参考博客：https://www.liuchuo.net/archives/2090post
基于这位大佬（同时应该也是位超可爱的小姐姐） 的代码，作个解释：spa
核心思路：.net
数据存储：利用数组来存储数，利用左儿子下标是根节点下标二倍，右儿子下标是根节点下标的二倍加一，来组织数据。code
思路：因为根节点是在后序序列中找的，因此肯定完根节点，在中序序列中找到这个根节点，而后找到该根节点对应的左右子树的大小（注意：这里咱们只须要算出左右子树的大小就能够，由于知道左右子树的大小，就能够求出根节点对应的左右子树本身的根节点：递归
图示为： （ ' * '符表明左子树的那一堆，' ^ '表明右子树的那一堆 ）ci
对于树（不管是整棵树仍是树的一个子树，都知足一下规律：）get
中序序列： ****根节点^^^^^^^ 博客
后序序列： ****^^^^^^^根节点
由上图，假设 left_len为左子树的大小，right_len为右子树的大小，根节点在后序序列中的下标为root
那么，左子树的根节点即为root - right_len-1；右子树的根节点即为 root-1 。
而后这一过程把中序序列分红两部分：左子树一部分 右子树一部分。故而递归求解：对于左子树，此时的start和end就变成了在中序序列里 由左子树的元素组成的那一段数据的集合的开始下标和结束下标。右子树也同理。
这时候可能有个疑问：为何只传中序序列里面的 左子树 or 右子树 所在的区域：
由于：你会发现：其实对于后序序列或者前序序列，他们都只对构造二叉树起一种做用：即：提供树根 root 是什么 .因此，对于前序序列和后序序列来讲它们的做用就是找根，找到根，再到中序序列里面找到 对应 左右子树 的长度。 而后再回来到后序序列（或前序序列）中，利用 root 在后序序列（或前序序列）中的位置，结合刚求出的左右子树的长度，找到 root 对应的左右子树的根root 。因此，其实求根这一步并不须要咱们知道对于后序序列（或前序序列）中对应的左右子树的那一堆元素从哪开始从哪结束（实际上是能够算出来的，可是算出来也没用啊，因此不必卸载参数列表里了，由于明明一个参数root就能够肯定出来两棵子树的根节点在哪里了嘛~ ）
那为何中序序列就必须知道左右子树对应的元素是从哪到哪的呢？由于中序序列是根据root把序列分红左右两个部分，若是没有 start 和 end 怎么肯定 左子树的开始和右子树的结束，也就无法肯定左右子树的长度了 ，因此这两个参数必须得传，并且还要在递归时变成更小的范围 。
==============================================================================
有一道例题：
https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072
这个题的ac代码
#include <iostream>
#include <string.h>
using namespace std;
int a[100000];
int post[35];
int in[35];
void travel(int root,int index,int start,int endd)
{
if(start>endd)
return;
a[index]=post[root];
int key=start;
while( key<endd && in[key]!=post[root] )
{
key++;
}
int left_len=key-start;
int right_len=endd-key;
travel(root-endd+key-1,index*2,start,key-1);
travel(root-1,index*2+1,key+1,endd);
}
int main()
{
int n;
cin>>n;
memset(a,-1,sizeof(a));
for(int i=1;i<=n;i++)
{
cin>>post[i];
}
for(int i=1;i<=n;i++)
{
cin>>in[i];
}
travel( n,1,1,n );
int cnt=0;
int i=2;
for(int i=1;i<=100000;i++)
{
if( a[i]!=-1 )
{
if(cnt!=0)
printf(" ");
printf("%d", a[i]);
cnt++;
}
if(cnt==n)
break;
}
cout<<endl;
return 0;
}
而后这个题有几个坑，
首先，就我这里储存树的数组a[ ]必定要开的大，我开了1000最后一个数据也是答案错误，开了100000终于对了，，，，因此，之后这种不知道有多大的，开大点吧，并且，若是就一个数据错了的时候，先想一想是否是数组开小了。或者题目有特判：重读题或者是想象会不会有什么其余状况，好比说能够是0，或者数对（a，b）并不必定是a<b ，，，之类的