给二叉树的前序和中序遍历,重建出该二叉树(不含重复的数字)
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
Tnode *rebuild_tree(int *pre, int pre_left, int pre_right, int *vin, int vin_left, int vin_right)
{
printf("pre: left-%d, right-%d, vin: left-%d, right-%d, pre-val:%d.\n", pre_left,pre_right,vin_left,vin_right, pre[pre_left]);
if(pre_left>pre_right || vin_left>vin_right) return NULL;
Tnode *root = (Tnode *)calloc(1, sizeof(Tnode));
root->val = pre[pre_left];
int mid = 0;
for (mid=vin_left; mid<=vin_right; mid++)
{
if(vin[mid] == pre[pre_left])
{
printf("\n****vin (pre_left-%d, mid:%d-%d).****\n", pre_left, mid, vin[mid]);
if (mid>vin_left) {
printf("left.");
//(mid-vin_left)根结点左边有几个元素
root->left = rebuild_tree(pre, pre_left+1, pre_left+(mid-vin_left), vin, vin_left, mid-1);
}
if (mid<vin_right) {
printf("right.");
//(pre_left+(mid-vin_left))为从pre_left开始往后推这么多元素
root->right = rebuild_tree(pre, (pre_left+(mid-vin_left))+1, pre_right, vin, mid+1, vin_right);
}
break;
}
}
return root;
}