105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 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;

}