给定一个前序和中序变量的结果，写一个算法重建这棵树：
前序： a b d c e f中序: d b a e c f
前序遍历的每一个节点，都是当前子树的根节点，同时，以对应的节点为边界，就会把前序遍历的结果分为左子树和右子树。
a是前序中第一个节点，以a为中界，把中序的结果分成：左：db右:ecf
对于db，由于在前序中b在d前面，所以，b是d的父亲。
对于ecf，前序中c在前面，c为父亲，c把e和f分开。
代码：
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
typedef struct Node{
Node* left;
Node* right;
char data;
Node(char c)
{
data=c;
left=NULL;//很重要
right=NULL;
}
~Node()
{
delete left;//如果left为null，也没问题，delete兼容null
delete right;
}
}*BiTree;
#define TREELEN 6
Node* rebuild(char *preOrder,char *inOrder,int n)
{
if(n==0) return NULL;
//获得前序遍历的第一个节点
char c=preOrder[0];
Node *node=new Node(c); //This is the root node of this tree/sub tree.
int i;
for( i=0;i<n && inOrder[i]!=c;i++)
;
int lenL=i; //// the node number of the left child tree.
int lenR=n-i-1;//// the node number of the rigth child tree.
//为什么减1，因为中间的元素占了一个
if(lenL>0)
node->left=rebuild(&preOrder[1],&inOrder[0],lenL);
if(lenR>0)
node->right=rebuild(&preOrder[lenL+1],&inOrder[lenL+1],lenR);
return node;
}
void levelOrder(BiTree T)
{
queue<BiTree> q;
q.push(T);
while(!q.empty())
{
BiTree h=q.front();q.pop();
cout<<h->data<<ends;
if(h->left) q.push(h->left);
if(h->right) q.push(h->right);
}
}
int main()
{
char szPreOrder[TREELEN]={'a','b','d','c','e','f'};
char szInOrder[TREELEN]={ 'd', 'b','a','e','c','f'};
Node *result=rebuild(szPreOrder,szInOrder,6);
cout<<endl;
levelOrder(result);
}
注意当n==0，时，我们要返回
if(n==0) return NULL;不能写成return；否则错误。关键的代码为：由于根节点把左子树和右子树分开了：
if(lenL>0)
node->left=rebuild(&preOrder[1],&inOrder[0],lenL);
if(lenR>0)
node->right=rebuild(&preOrder[lenL+1],&inOrder[lenL+1],lenR);
在建右子树时，我们从preOrder[lenL+1] 开始，因为前面的都是左子树的节点，这点要特别注意。
递归过程：
rebuild(pre[0],in[0],6)`` 第一次建立a节点,lenL=2 ,lenR=3rebuild(pre[1],inorder[0],2)建立节点b，在db中找b，lenL=1,lenR=0;b->left=rebuild(pre[d],inorer[0],1)```
建立节点d，lenL=0;lenR=0;d的左子树和右子树都为空。递归返回。
建立a的右子树
a->right=rebuild(preOrder[3,inOrder[3],3);
参考：http://blog.chinaunix.NET/uid-1844931-id-3033009.html
更多：
http://www.cppblog.com/flyinghearts/archive/2010/08/16/123544.html
非递归：
http://zhangzhibiao02005.blog.163.com/blog/static/37367820201122833633997/
扩展问题1：如果前序和中序遍历的字母有重复的，那么怎么构造所有可能的解呢？
扩展问题2：如何判断给定的前序遍历和中序遍历的结果是合理的？
扩展问题3：如果知道前序和后序的结果，能重构二叉树吗？
思路：
问题1：搜索所有可能的情况，并调用扩展问题2的解决方案，判断此情况是否合理（剪枝操作），如果合法，则构造解
问题2：递归判断左右子树是否合理，递归的返回条件是到达叶子节点。
更多：http://blog.csdn.Netvividonly/article/details/6688327
http://www.wcode.net/plus/view.PHP?aid=704720
递归算法实现，分别遍历左右子树，递归中迭代查找左右子树的长度，类似于书中的方法。
#include <iostream>
#include <string>
using namespace std;
bool valid = true;
inline int find(char needle, const char* haystack, int start, int end )
{
const char* p = haystack + start;
int i = 0;
int offset = end - start ;
while ( p && i < offset )
{
if ( *p == needle )
{
if ( start != 0 )
return i + start;
else
return i;
}
p++, i++;
}
return -1;
}
void isValid( const char* preOrder, const char* inOrder, int start, int end )
{
if ( !valid )
return ;
int position = find( *preOrder, inOrder, start,end );
if ( position == -1 )
{
valid = false;
return ;
}
if ( start < position )
{
isValid( preOrder + 1, inOrder,start,position ); //在左子树中遍历
}
if ( position + 1 < end )
{
isValid( preOrder + position + 1, inOrder, position + 1, end ); //在右子树中遍历
}
}
// Two Simple Test Cases
int main()
{
string pre1 = "abdefc";
string mid1 = "dbfeac";
string pre2 = "abdefc";
string mid2 = "dcfeab";
isValid(pre1.c_str(),mid1.c_str(),0,mid1.length());
cout << valid << endl; // 输出 true
valid = true;
isValid(pre2.c_str(),mid2.c_str(),0,mid2.length());
cout << valid << endl; //输出false
return 0;
}
已知中序和后序，更多：
http://www.cppblog.com/wanghaiguang/archive/2012/05/24/176012.aspx
（下面的这篇来自)http://biaobiaoqi.me/blog/2013/04/27/pat1020-pat1043-rebuild-binary-tree/
背景
《二叉树的遍历（递归、非递归）分析》总结了二叉树不同遍历方式的递归和非递归实现，本文则讨论如何针对不同遍历方式的组合重建二叉树。为了简化问题的考虑，假定二叉树中不会出现重复值。列入考虑范围的有前序、中序、后序、层序遍历这四种的组合。前中后序比较常见，而层序则相对特殊一点了。
PAT 的 1043 和 1020 题是遍历相关的模板题，正好派上用场。
中序+前序
算法描述：
初始：用前序遍历序列确定根节点，在中序遍历序列中找到该根节点，则左右子树分别为中序中该节点左右的序列。
迭代：对各个子树分别执行三步操作，1.在前序序列中找子树的根节点；2。在中序序列中找子树的根节点，并划分开根节点的左右子树；3.根据新生成的左右子树，在前序序列中划分开这些节点，从而得到了两颗子树的前序、中序序列。
练习：PAT1043:Is It a Binary Search Tree
题意：
输入一个树的前序遍历序列，判定这个树是否是二叉搜索树或者 BST 的镜像树，如果是，则用后序序列输出。
解题思路：
1.BST 很特殊，实质上 BST 的所有节点的顺序排列就是中序遍历了。
2.要检查树是否是 BST 或者镜像 BST，只需按照重建树的思路，在每次重建的过程中做适当检查即可。检查思路是：检查前序遍历序列中，根节点之后的节点排序是否符合 BST 的二分规则（即前一段都是小于根节点的，后一段都是大于根节点的）。
3.最后的输出是后序遍历。过程中其实并不用构建整个树，直接在处理过程中，按后序的方式存储节点到队列中即可。
有了这些考虑，就可以写出代码啦。详细解题代码见链接 PAT1043
中序+后序
算法描述：
初始：用后序遍历序列确定根节点，在中序遍历序列中找到该根节点，则左右子树分别为中序中该节点左右的序列。
迭代：对各个子树分别执行三步操作，1.在后序序列中找子树的根节点；2。在中序序列中找子树的根节点，并划分开根节点的左右子树；3.根据新生成的左右子树，在后序序列中划分开这些节点，从而得到了两颗子树的后序、中序序列。
练习：PAT1020:Tree Traversals
题意：
输入为一棵二叉树的后序遍历序列和中序遍历序列。求树的前序遍历序列。
解题思路：
1.有了中序和后序，就能重建树。
2.最后的输出是层序遍历。过程中其实并不用构建整个树。直接在处理过程中，按层序的方式存储节点到队列中即可。
详细解题代码见链接 PAT1020
中序+层序
算法描述：
初始：用层序遍历确定顶节点，在中序遍历中，利用顶节点划分出左右子树。
迭代：对各个子树分别执行三步操作，1.在层序序列中，找出子树节点集合中，最靠前的节点，这个节点即为子树的顶节点；2.在中序序列中找 1 中得到的顶节点，并划分开顶节点的左右子树；
跟（中序+前序）和（中序+后序）不同之处在于没有迭代的第 3 步，层序是无法直接划分得到左右子树的节点集合的。但这并不妨碍正常的处理。层序是用来找到子树的顶节点的，而顶节点即是所有子树的节点中，在层序遍历中最靠前的节点。
前序+后序
这个组合是无法重建确定的二叉树的。
对于满二叉树，利用子树节点的排列顺序能区分开左右子树节点集合，构建是没有问题的。但一旦有单个叶子的节点存在，则无法确定叶子是左儿子还是右儿子。因为无论是前序还是后序序列，都无法体现单个儿子情况下，儿子的位置。前序会将左右子树的点置于节点之后，后序则是将左右子树的点置于节点之前。
举个简单的反例：
给出如下的前序序列和后序序列： preorder: A, B; postorder: B, A
能构建的二叉树有两种可能，1.A 是根节点，B 是 A 左儿子； 2.A 是根节点， B 是 A 的右儿子。无法得到一个唯一的结果。
前序+层序
这个组合也是无法重建确定的二叉树的。同样于后序+层序的情况。
道理跟（前序+后序）的道理一样，无论是前序、后序，还是层序，都是无法确定单个儿子节点情况下儿子节点的顺序。
总结
中序遍历配合另外任何一个遍历，能重建二叉树。其他的任意两个序列的组合都不能唯一的确定重建的二叉树。
