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

做题思路：切割数组，递归解决

递归结束条件：传入的数组大小为0，返回NULL

1. 找到前序遍历数组的第一个元素， 创建结点。左右孩子设置为NULL。
2. 若前序遍历数组的大小为1，返回该结点
3. 根据该结点切割中序遍历数组，将中序遍历数组分割成左右两个数组。算出他们的各自大小
4. 根据中序遍历数组左右数组的各子大小切割前序遍历数组。也分为左右数组
5. 递归进入左右数组，将返回的结果作为根结点的左右孩子
6. 返回根节点

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    // 递归结束条件：传入的数组大小为0
    if(!preorderSize)
        return NULL;
    // 1.找到前序遍历数组的第一个元素， 创建结点。左右孩子设置为NULL。
    int rootValue = preorder[0];
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootValue;
    root->left = NULL;
    root->right = NULL;
    // 2.若前序遍历数组的大小为1，返回该结点
    if(preorderSize == 1)
        return root;
    // 3.根据该结点切割中序遍历数组，将中序遍历数组分割成左右两个数组。算出他们的各自大小
    int index;
    for(index = 0; index < inorderSize; index++) {
        if(inorder[index] == rootValue)
            break;
    }
    int leftNum = index;
    int rightNum = inorderSize - index - 1;

    int* leftInorder = inorder;
    int* rightInorder = inorder + leftNum + 1;
    // 4.根据中序遍历数组左右数组的各子大小切割前序遍历数组。也分为左右数组
    int* leftPreorder = preorder+1;
    int* rightPreorder = preorder + 1 + leftNum; 
    // 5.递归进入左右数组，将返回的结果作为根结点的左右孩子
    root->left = buildTree(leftPreorder, leftNum, leftInorder, leftNum);
    root->right = buildTree(rightPreorder, rightNum, rightInorder, rightNum);
    // 6.返回根节点
    return root;
}