代码
1 class Solution {
2 public:
3 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
4 if(preorder.size() == 0) return NULL;
5 //找根结点
6 int rootValue = preorder[0];
7 TreeNode *root = new TreeNode(rootValue);
8 if(preorder.size() == 1) return root;
9
10 //找到根结点在中序数组中的位置，作为分割点
11 int Index;
12 for(int i = 0;i < inorder.size();i++){
13 if(rootValue == inorder[i]) {Index = i;break;}
14 }
15
16 //对中序数组进行分割，左闭右开原则
17 vector<int>leftInorder(inorder.begin(),inorder.begin()+Index); //[0,Index)
18 vector<int>rightInorder(inorder.begin()+Index+1,inorder.end()); //[Index+1,end)
19
20 //对前序数组进行分割，左闭右开原则,用中序分割后的左右数组个数来分割前序数组
21 preorder.erase(preorder.begin()); //开头元素没有用，舍弃
22 vector<int>leftPreorder(preorder.begin(),preorder.begin()+leftInorder.size());
23 //[0,leftInorder.size)
24 vector<int>rightPreorder(preorder.begin()+leftInorder.size(),preorder.end());
25 //[leftInorder.size(),preorder.end)
26
27 //递归处理左、右
28 root->left = buildTree(leftPreorder,leftInorder);
29 root->right = buildTree(rightPreorder,rightInorder);
30 return root;
31 }
32 };
参考LeetCode106