给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
解题代码如下：
int root_preorder(int *preorder,int left,int right){
return preorder[left];
}
int find_root(int* inorder,int left,int right,int val){
int i;
for(i=left;i<=right;i++){
if(inorder[i]==val){
return i;
}
}
return 0;
}
int find_pre(int* preorder,int preleft,int preright,int* inorder,int inleft,int inright){
int i;
int j;
for(i=preleft;i<=preright;i++){
for(j=inleft;j<=inright;j++){
if(preorder[i]==inorder[j]){
return i;
}
}
}
return 0;
}
void create_tree_dfs(int* preorder,int preleft,int preright,int* inorder,int inleft,int inright,struct TreeNode **r){
if(preleft<=preright){
int val=root_preorder(preorder,preleft,preright);
(*r)->val=val;
(*r)->left=(struct TreeNode* )malloc(sizeof(struct TreeNode));
(*r)->right=(struct TreeNode* )malloc(sizeof(struct TreeNode));
int in_root_index=find_root(inorder,inleft,inright,val);
int left_index=find_pre(preorder,preleft,preright,inorder,inleft,in_root_index-1);
// printf("left_index %d |",left_index);
create_tree_dfs(preorder,left_index,left_index+in_root_index-inleft-1,inorder,inleft,in_root_index-1,&((*r)->left));
int right_index=find_pre(preorder,preleft,preright,inorder,in_root_index+1,inright);
// printf("right_index %d |",right_index);
create_tree_dfs(preorder,right_index,right_index+inright-in_root_index-1,inorder,in_root_index+1,inright,&((*r)->right));
}
else{
*(r)=NULL;
}
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
struct TreeNode* r=(struct TreeNode* )malloc(sizeof(struct TreeNode));
create_tree_dfs(preorder,0,preorderSize-1,inorder,0,inorderSize-1,&r);
return r;
}
