1. 云栖社区>
2. >
3. 正文

# 二叉树专题-根据前序和中序序列构造二叉树

```/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public:
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
if(preorder.empty()||inorder.empty())
return NULL;
return build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
}
TreeNode* build(vector<int> preorder,vector<int> inorder,int preL,int preR,int inL,int inR){
if(preL>preR)//终止条件
return NULL;
int rootValue=preorder[preL];//先序第一个值即为根的值
TreeNode* root=new TreeNode(rootValue);
//寻找左右子树的划分
int k;
for(int i=0;i<inorder.size();++i){
if(rootValue==inorder[i]){
k=i;
break;
}
}
int numLeft=k-inL;
root->left=build(preorder,inorder,preL+1,preL+numLeft,inL,k-1);
root->right=build(preorder,inorder,preL+numLeft+1,preR,k+1,inR);
return root;
}
};```

40+云计算产品，6个月免费体验