106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

这一题其实代码写起来可能挺复杂，需要画一些时间
解题代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 int root_mid(int left,int right,int val,int *inorder){
     int i;
     for(i=left;i<=right;i++){
         if(inorder[i]==val){
             return i;
         }
     }
     return 0;
 }
 int post_position(int *postorder,int left,int right,int inleft,int inright,int *inorder ){
     int i;
     int j;
     for(i=left;i<=right;i++){
         for(j=inleft;j<=inright;j++){
            if(postorder[i]==inorder[j]){
                return i;
            }
         }
        
     }
     return 0;
 }

 void dfs(int* inorder, int instart,int inend, int* postorder, int postart,int poend,struct TreeNode **r){
 if(inend>=instart){

     int val=postorder[poend];
     (*r)->val=val;
     int mid=root_mid(instart,inend,val,inorder);
     (*r)->left=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    (*r)->right=(struct TreeNode*)malloc(sizeof(struct TreeNode));
  
    int left_po=post_position(postorder,postart,poend,instart,mid-1,inorder);
    dfs(inorder, instart,mid-1,postorder, left_po,left_po+mid-instart-1,&((*r)->left));
    int right_po=post_position(postorder,postart,poend,mid+1,inend,inorder);
      dfs(inorder,mid+1,inend,postorder,right_po,right_po+inend-mid-1,&((*r)->right));
     }
     else{
         (*r)=NULL;

     }
 }
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
struct TreeNode* r=(struct TreeNode*)malloc(sizeof(struct TreeNode));
     dfs(inorder,0,inorderSize-1,postorder,0,postorderSize-1,&r);
     return r;




}