給定一個前序和中序變量的結果，寫一個算法重建這棵樹：
前序： a b d c e f中序: d b a e c f
前序遍歷的每一個節(jié)點篷角，都是當前子樹的根節(jié)點巍膘，同時，以對應的節(jié)點為邊界摩钙，就會把前序遍歷的結果分為左子樹和右子樹。
a是前序中第一個節(jié)點查辩，以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;
//獲得前序遍歷的第一個節(jié)點
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；否則錯誤麦萤。關鍵的代碼為：由于根節(jié)點把左子樹和右子樹分開了：
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] 開始，因為前面的都是左子樹的節(jié)點壮莹，這點要特別注意翅帜。
遞歸過程：
rebuild(pre[0],in[0],6)`` 第一次建立a節(jié)點,lenL=2 ,lenR=3rebuild(pre[1],inorder[0],2)建立節(jié)點b，在db中找b命满，lenL=1,lenR=0;b->left=rebuild(pre[d],inorer[0],1)```
建立節(jié)點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：搜索所有可能的情況讯榕，并調(diào)用擴展問題2的解決方案，判斷此情況是否合理（剪枝操作）匙睹，如果合法愚屁，則構造解
問題2：遞歸判斷左右子樹是否合理，遞歸的返回條件是到達葉子節(jié)點痕檬。
更多：http://blog.csdn.Netvividonly/article/details/6688327
http://www.wcode.net/plus/view.PHP?aid=704720
遞歸算法實現(xiàn)霎槐，分別遍歷左右子樹，遞歸中迭代查找左右子樹的長度梦谜，類似于書中的方法丘跌。
#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/
背景
《二叉樹的遍歷（遞歸、非遞歸）分析》總結了二叉樹不同遍歷方式的遞歸和非遞歸實現(xiàn)闭树，本文則討論如何針對不同遍歷方式的組合重建二叉樹耸棒。為了簡化問題的考慮，假定二叉樹中不會出現(xiàn)重復值报辱。列入考慮范圍的有前序与殃、中序、后序碍现、層序遍歷這四種的組合幅疼。前中后序比較常見，而層序則相對特殊一點了昼接。
PAT 的 1043 和 1020 題是遍歷相關的模板題爽篷，正好派上用場。
中序+前序
算法描述：
初始：用前序遍歷序列確定根節(jié)點慢睡，在中序遍歷序列中找到該根節(jié)點逐工，則左右子樹分別為中序中該節(jié)點左右的序列。
迭代：對各個子樹分別執(zhí)行三步操作一睁，1.在前序序列中找子樹的根節(jié)點钻弄；2。在中序序列中找子樹的根節(jié)點者吁，并劃分開根節(jié)點的左右子樹窘俺；3.根據(jù)新生成的左右子樹，在前序序列中劃分開這些節(jié)點复凳，從而得到了兩顆子樹的前序瘤泪、中序序列。
練習：PAT1043:Is It a Binary Search Tree
題意：
輸入一個樹的前序遍歷序列育八，判定這個樹是否是二叉搜索樹或者 BST 的鏡像樹对途，如果是部默，則用后序序列輸出可缚。
解題思路：
1.BST 很特殊骑丸，實質(zhì)上 BST 的所有節(jié)點的順序排列就是中序遍歷了步鉴。
2.要檢查樹是否是 BST 或者鏡像 BST浸卦，只需按照重建樹的思路修械，在每次重建的過程中做適當檢查即可束亏。檢查思路是：檢查前序遍歷序列中蜂林，根節(jié)點之后的節(jié)點排序是否符合 BST 的二分規(guī)則（即前一段都是小于根節(jié)點的签则，后一段都是大于根節(jié)點的）须床。
3.最后的輸出是后序遍歷。過程中其實并不用構建整個樹渐裂，直接在處理過程中豺旬，按后序的方式存儲節(jié)點到隊列中即可钠惩。
有了這些考慮，就可以寫出代碼啦族阅。詳細解題代碼見鏈接 PAT1043
中序+后序
算法描述：
初始：用后序遍歷序列確定根節(jié)點篓跛，在中序遍歷序列中找到該根節(jié)點，則左右子樹分別為中序中該節(jié)點左右的序列耘分。
迭代：對各個子樹分別執(zhí)行三步操作举塔，1.在后序序列中找子樹的根節(jié)點；2求泰。在中序序列中找子樹的根節(jié)點央渣，并劃分開根節(jié)點的左右子樹；3.根據(jù)新生成的左右子樹渴频，在后序序列中劃分開這些節(jié)點芽丹，從而得到了兩顆子樹的后序、中序序列卜朗。
練習：PAT1020:Tree Traversals
題意：
輸入為一棵二叉樹的后序遍歷序列和中序遍歷序列拔第。求樹的前序遍歷序列。
解題思路：
1.有了中序和后序场钉，就能重建樹蚊俺。
2.最后的輸出是層序遍歷。過程中其實并不用構建整個樹逛万。直接在處理過程中泳猬，按層序的方式存儲節(jié)點到隊列中即可。
詳細解題代碼見鏈接 PAT1020
中序+層序
算法描述：
初始：用層序遍歷確定頂節(jié)點宇植，在中序遍歷中得封，利用頂節(jié)點劃分出左右子樹。
迭代：對各個子樹分別執(zhí)行三步操作指郁，1.在層序序列中忙上，找出子樹節(jié)點集合中，最靠前的節(jié)點闲坎，這個節(jié)點即為子樹的頂節(jié)點疫粥；2.在中序序列中找 1 中得到的頂節(jié)點，并劃分開頂節(jié)點的左右子樹腰懂；
跟（中序+前序）和（中序+后序）不同之處在于沒有迭代的第 3 步梗逮，層序是無法直接劃分得到左右子樹的節(jié)點集合的。但這并不妨礙正常的處理悯恍。層序是用來找到子樹的頂節(jié)點的库糠，而頂節(jié)點即是所有子樹的節(jié)點中伙狐，在層序遍歷中最靠前的節(jié)點涮毫。
前序+后序
這個組合是無法重建確定的二叉樹的瞬欧。
對于滿二叉樹，利用子樹節(jié)點的排列順序能區(qū)分開左右子樹節(jié)點集合罢防，構建是沒有問題的艘虎。但一旦有單個葉子的節(jié)點存在，則無法確定葉子是左兒子還是右兒子咒吐。因為無論是前序還是后序序列野建，都無法體現(xiàn)單個兒子情況下，兒子的位置恬叹。前序會將左右子樹的點置于節(jié)點之后候生，后序則是將左右子樹的點置于節(jié)點之前。
舉個簡單的反例：
給出如下的前序序列和后序序列： preorder: A, B; postorder: B, A
能構建的二叉樹有兩種可能绽昼，1.A 是根節(jié)點唯鸭，B 是 A 左兒子； 2.A 是根節(jié)點硅确， B 是 A 的右兒子目溉。無法得到一個唯一的結果。
前序+層序
這個組合也是無法重建確定的二叉樹的菱农。同樣于后序+層序的情況缭付。
道理跟（前序+后序）的道理一樣，無論是前序循未、后序陷猫，還是層序，都是無法確定單個兒子節(jié)點情況下兒子節(jié)點的順序只厘。
總結
中序遍歷配合另外任何一個遍歷烙丛，能重建二叉樹。其他的任意兩個序列的組合都不能唯一的確定重建的二叉樹羔味。
