# LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

```preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]```

Return the following binary tree:

```    3
/ \
9  20
/  \
15   7

```class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

vector<int> leftpre;
vector<int> leftino;
vector<int> rightpre;
vector<int> rightino;

if(preorder.empty()||inorder.empty())
return NULL;
int root = preorder[0]; int left=0;int right=0;int tag=0;
for(int i=0;i<inorder.size();i++)
{
if(inorder[i]==root)
{
tag=1;
}
else if(tag==0)
{left++;leftino.push_back(inorder[i]);}
else
{right++;rightino.push_back(inorder[i]);}
}
for(int i=1;i<left+1;i++)
{
leftpre.push_back(preorder[i]);
}
for(int i=left+1;i<preorder.size();i++)
{
rightpre.push_back(preorder[i]);
}

TreeNode* tree = new TreeNode(root);

tree->left = buildTree(leftpre,leftino);
tree->right = buildTree(rightpre,rightino);

return tree;

}
};```

0 条评论

13330

29240

16070

32040

11630

16440

19760

12840

12530

17340