不用迭代器的代码
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
TreeNode* root = NULL;
int length_pre = pre.size();
int length_vin = vin.size();
if(length_pre <= || length_vin <= )
return root;
return ConstructCore(pre,vin,,length_pre-,,length_vin-);
}
TreeNode* ConstructCore(vector<int> pre,vector<int> vin,int start_pre,int end_pre,int start_vin,int end_vin){
int rootval = pre[start_pre];
TreeNode* root = new TreeNode(rootval);
if(start_pre == end_pre || start_vin == end_vin)
return root;
int mid;
for(int i = start_vin;i <= end_vin;i++){
if(pre[start_pre] == vin[i]){
mid = i;
break;
}
}
if(mid > start_vin)
root->left = ConstructCore(pre,vin,start_pre+,mid-start_vin+start_pre,start_vin,mid-);
if(end_vin > mid)
root->right = ConstructCore(pre,vin,mid-start_vin+start_pre+,end_pre,mid+,end_vin);
return root;
}
};
mid是在vin中的索引,与pre相关的只是个数,所以用mid-start_vin来表示有多少个,然后再加上之前的开始坐标