/**
* rebuild binary tree from inorder and preorder sequence
**/
struct binary_tree_node *
rebuild_binary_tree_pre(int n, int inOrderSeq[], int preOrderSeq[])
{
// root value
int value = preOrderSeq[0];
// count left subtree nodes
int lefts = n;
for (int i=0; i<n; i++) {
if (inOrderSeq[i] == value) {
lefts = i;
break;
}
}
// bad seq
if (lefts == n) {
return NULL;
}
// calculate right subtree nodes
int rights = n - 1 - lefts;
struct binary_tree_node *left = NULL;
struct binary_tree_node *right = NULL;
// rebuild left subtree recursively
if (lefts > 0) {
left = rebuild_binary_tree_pre(lefts, inOrderSeq, preOrderSeq+1);
if (left == NULL) {
return NULL;
}
}
// rebuild left subtree recursively
if (rights > 0) {
right = rebuild_binary_tree_pre(rights, inOrderSeq+lefts+1, preOrderSeq+lefts+1);
if (right == NULL) {
free_tree(left);
return NULL;
}
}
// allocate memory for root node
struct binary_tree_node *root = (struct binary_tree_node *)malloc(sizeof(struct binary_tree_node));
if (root == NULL) {
free_tree(left);
free_tree(right);
return NULL;
}
// set root node fields
root->value = value;
root->left= left;
root->right = right;
return root;
}