【二叉树】从中序与后序遍历构造二叉树

做题思路：递归解决

1.如果后序数组为空，返回NULL

2.先确定根结点在后序遍历数组中的位置，创立结点

3.在中序遍历中找到该值，作为切割点

4.切割中序遍历数组，切割成中序左数组和中序右数组

5.根据中序左数组和中序右数组的大小来在后序遍历数组中切割左后序遍历数组和右后序遍历数组

6.将中序左数组和后续左数组作为参数进行递归，返回的结点为当前根结点的左孩子

7.将中序右数组和后序右数组作为参数进行递归，返回的结点为当前根结点的右孩子

8.返回根结点

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    //1.如果后序数组为空，返回NULL
    if(postorderSize <= 0)
        return NULL;
    //2.先确定根结点在后序遍历数组中的位置，创立结点
    int rootValue = postorder[postorderSize - 1];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootValue;
    root->left = NULL;
    root->right = NULL;

    if(postorderSize == 1)
        return root;
    //3.在中序遍历中找到该值，作为切割点
    int delimiterIndex;
    for(delimiterIndex = 0; delimiterIndex < inorderSize; delimiterIndex++) {
        //当数组中元素等于后序数组中最后一个时，
        if(inorder[delimiterIndex] == rootValue)
            break;
    }
    //4.切割中序遍历数组，切割成中序左数组和中序右数组
    int* inorderLeftArr = inorder;
    int* inorderRightArr = inorder + delimiterIndex + 1;
    int leftArrNum = delimiterIndex;
    int rightArrNum = inorderSize-delimiterIndex-1;
    //5.根据中序左数组和中序右数组的大小来在后序遍历数组中切割左后序遍历数组和右后序遍历数组
    int * postorderArr = postorder;
    int* postorderRightArr = postorder + delimiterIndex;
    //6.将中序左数组和后续左数组作为参数进行递归，返回的结点为当前根结点的左孩子
    root->left = buildTree(inorderLeftArr, leftArrNum, postorderArr, leftArrNum);
    //7.将中序右数组和后序右数组作为参数进行递归，返回的结点为当前根结点的右孩子
    root->right =buildTree(inorderRightArr, rightArrNum, postorderRightArr, rightArrNum);
    return root;
}