问题描述：
由前序遍历和中序遍历重建二叉树（前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）数据不含重复值。
题目分析如下：
前序遍历序列1 2 3 4 5 6，前序遍历规则是根--左--右。
中序遍历序列3 2 4 1 6 5，中序遍历规则是左--根--右
1.由前序遍历可知根节点一定为第一个元素1，在中序遍历序列中找到1对应位置，判断根节点1的左右子树是否为空，1的左右都不为空，1的左边就是左子树324，右边就是右子树56；
2.再根据前序遍历规则可知，左子树序列里第一个就是左子树的根节点2，右子树序列里的第一个就是右子树的根节点5，用上次的方法递归建立左右子树。
3.再根据中序遍历序列可知，左子树的根节点2左边的一定是以其为根节点的左子树序列3，右边就是以其为根节点的右子树序列4，
右子树的根节点5左边的一定是以其为根节点的右子树序列6，直至序列为空，就可以完整重建二叉树了
代码实现：
#include<iostream> #include<cassert> using namespace std; struct NewTreeNode { NewTreeNode* _left; NewTreeNode* _right; int _value; NewTreeNode(int value) :_value(value) ,_left(NULL) ,_right(NULL) {} }; typedef NewTreeNode Node; Node* _RebuildTree(int *startPre,int *endPre,int *startIn,int *endIn) { Node *root = new Node(startPre[0]); //_left和_right已初始化为NULL if(startIn == endIn && *startIn == *startIn) { return root; } //4.根据此根节点在中序中找此节点的位置 int * rootIn = startIn; while(*startPre != *rootIn) { rootIn++; } //根据此根节点在中序遍历中的位置，递归还原左子树 int leftlen = rootIn-startIn; if(leftlen>0) { root->_left = _RebuildTree(startPre+1,startPre+leftlen,startIn,startIn+leftlen-1); } if(leftlen+startIn < endIn)//该节点还存在右子树，所以继续递归还原右子树 {//递归还原右子树 root->_right = _RebuildTree(startPre+leftlen+1,endPre,startIn+leftlen+1,endIn); } return root; } Node* RebuildTree(int* PreOrder,int* InOrder,int len) { if(PreOrder == NULL || InOrder == NULL ) return NULL; else return _RebuildTree(PreOrder,PreOrder+len-1,InOrder,InOrder+len-1); } void PostOrder(Node *root) { if(root->_left != NULL) PostOrder(root->_left); if(root->_right != NULL) PostOrder(root->_right); cout<<root->_value<<" "; } void PrevOrder(Node *root) { if(root==NULL) return; cout<<root->_value<<" "; if(root->_left != NULL) PrevOrder(root->_left); if(root->_right != NULL) PrevOrder(root->_right); } int main() { int PreOrder[] = {1,2,3,4,5,6}; int InOrder[] = {3,2,4,1,6,5}; int PreSize=sizeof(PreOrder)/sizeof(PreOrder[0]); int InSize=sizeof(InOrder)/sizeof(InOrder[0]); if(PreSize!=InSize) { cout<<"所给数据错误"<<endl; return -1; } NewTreeNode* root = RebuildTree(PreOrder,InOrder,PreSize); PrevOrder(root);//123456 cout<<endl; PostOrder(root);//342651 cout<<endl; system("pause"); return 0 ; } 在此运用前序和后序检查该树是否正确
运行结果：
未完，后续还有部分关于二叉树面试题！待续！
