# 题目：

```struct BinaryTreeNode{
int val;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x):val(x),left(NULL),right(NULL){}
};
```

# 代码：

```struct BinaryTreeNode{
int val;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x):val(x),left(NULL),right(NULL){}
};

BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder){
int rootValue=startPreorder[0];
BinaryTreeNode* root=new BinaryTreeNode(rootValue);
if(startPreorder==endPreorder && startInorder==endInorder)
return root;
//    else
//        throw std::exception("Invalid Input.\n");

int* rootInorder=startInorder;
while(rootInorder!=endInorder && *rootInorder!=rootValue)
++rootInorder;

//    if(rootInorder==endInorder && *rootInorder!=rootValue)
//        throw std::exception("Invalid Input.\n");

int leftLength=rootInorder-startInorder;
int* leftPreOrderEnd=startPreorder+leftLength;
if(leftLength>0)
root->left=ConstructCore(startPreorder+1,leftPreOrderEnd,startInorder,rootInorder-1);
int rightLength=endPreorder-startPreorder-leftLength;
if(rightLength>0)
root->right=ConstructCore(leftPreOrderEnd+1,endPreorder,rootInorder+1,endInorder);
return root;
}

BinaryTreeNode* Construct(int* preOrder,int* inOrder,int length){
if(preOrder==NULL || inOrder==NULL || length<=0)
return NULL;
return ConstructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1);
}
```

# 在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/8a19cbe657394eeaac2f6ea9b0f6fcf6?rp=1

AC代码：

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct TreeNode* construct(const vector<int> &pre,int startPre,int endPre,const vector<int> &in,int startIn,int endIn){
int rootValue=pre[startPre];
TreeNode* root=new TreeNode(rootValue);
if(startPre==endPre && startIn==endIn)
return root;

int rootIndex=startIn;
while(rootIndex<=endIn && in[rootIndex]!=rootValue)
rootIndex++;

int leftLength=rootIndex-startIn;
if(leftLength>0)
root->left=construct(pre,startPre+1,startPre+leftLength,in,startIn,rootIndex-1);
int rightLength=endPre-startPre-leftLength;
if(rightLength>0)
root->right=construct(pre,startPre+leftLength+1,endPre,in,rootIndex+1,endIn);

return root;
}

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int len=pre.size();
if(len<=0)
return NULL;
return construct(pre,0,len-1,in,0,len-1);
}
};
```

原文作者：AndyJee
原文地址: https://www.cnblogs.com/AndyJee/p/4624934.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。