1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
BinaryTreeNode* (int*preorder,int*inorder,int length){
if(preorder == NULL||inorder == NULL||length <= 0){
return NULL;
}
return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
BinaryTreeNode* ConstructCore(int *startPreorder,int*endPreorder,int*startInorder,int*endInorder){
int rootValue = startPreorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->value = rootValue;
root->lChild = NULL;
root->rChild = NULL;
if(startPreorder == endPreorder){
if(startInorder == endInorder&&*startPreorder == *startInorder){
return root;
}
else{
throw std::exception("Invalid input.");
}
}
int *rootInorder = startInorder;
while(rootInorder <= endInorder && rootInorder->value!=rootValue){
rootInorder++;
}
if(rootInorder == endInorder && rootInorder->value!=rootValue){
throw std::exception("Invalid Input");
}
int leftLength = rootInorder - startInorder;
int *leftPreorderEnd = startPreorder + leftLength;
if(leftLength > 0){
root->left = ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1);
}
if(leftLength < endPreorder - startPreorder){
root->right = ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder);
}
return root;
}
|
近期评论