# LeetCode题目：Construct Binary Tree from Preorder and Inorder Traversal

By | 2012 年 12 月 11 日

```   1
/   \
2     3
\    /
4  5
```

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.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
typedef TreeNode TN;
class Solution {
TN *buildTree(vector &preorder,int psi,int pei,
vector &inorder, int isi, int iei) {
if(pei - psi < 0 || pei - psi != iei - isi)
return NULL;
//root of sub tree
TN *root = new TN(preorder[psi]);
//find this value in inorder to locate the root in inorder
int riii = -1;//root index in inorder
for(int itemp = isi; itemp <= iei; ++ itemp) {
if(inorder[itemp] == root->val) {
riii = itemp;
break;
}
}
if(riii != -1) {
//calculate the nodes count in left tree
int leftCount = riii - isi;
TN *left = buildTree(preorder,psi + 1, psi + leftCount, inorder, isi, riii - 1);
root->left = left;
TN *right = buildTree(preorder,psi + leftCount + 1,pei, inorder, riii + 1, iei);
root->right = right;
}
return root;
}
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TN *root = buildTree(preorder,0,preorder.size() - 1,inorder,0,inorder.size() - 1);
}
};
```

## 3 thoughts on “LeetCode题目：Construct Binary Tree from Preorder and Inorder Traversal”

1. Roger

TreeNode *buildTree(vector &preorder, vector &inorder) {
TreeNode* root = myBuild(preorder, 0, preorder.size() – 1, inorder, 0, inorder.size() – 1);
}
TreeNode* myBuild(vector &preorder, int pstart, int pend, vector &inorder, int istart, int iend)
{
if(iend < istart)
return NULL;
TreeNode* root = new TreeNode(preorder[pstart]);
int i;
for( i = istart; i left = myBuild(preorder, pstart + 1, pstart + left_len, inorder, istart, i – 1);
root->right = myBuild(preorder, pstart + left_len + 1, pstart + left_len + right_len, inorder, i + 1, iend);
return root;
}

1. Roger

网页显示有问题 查找当前节点在inorder array中位置的for循环没有正常显示。关键就是直接找，找到break,不需要设置临时变量

1. uniEagle Post author

你把代码包含在<pre></pre>中就可以了，你试试。另外我没太明白你说的临时变量是指？