力扣889：根据先序和后序遍历构造二叉树
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1] 输出: [1]
上述例子用该代码模拟过程：
。
-
首先进入函数
constructFromPrePost，因为preorderSize不为0，所以为根节点分配内存空间，并设置根节点的值为preorder[0]，即1，此时root->val = 1，root->left和root->right都初始化为NULL。 -
然后因为
preorderSize > 1，进入内部的构建子树逻辑。开始遍历后序遍历数组找先序遍历数组中第二个元素（也就是2）的位置，找到后假设idx为2（因为在后序遍历数组中2是第三个元素，索引为2）。 -
接着递归构建左子树，调用
constructFromPrePost(preorder + 1, idx + 1, postorder, idx + 1)，这里相当于传入先序遍历数组的{2, 4, 5}（从第二个元素开始，长度为idx + 1 = 3）和后序遍历数组的{4, 5, 2}（从开头开始，长度为idx + 1 = 3）来构建以2为根节点的左子树。 -
之后判断
idx + 2 < preorderSize，这里idx + 2 = 4，小于preorderSize = 7，所以要构建右子树。调用constructFromPrePost(preorder + idx + 2, preorderSize - 2 - idx, postorder + idx + 1, postorderSize - 2 - idx)，即传入先序遍历数组的{3, 6, 7}（从idx + 2 = 4开始，长度为preorderSize - 2 - idx = 7 - 2 - 2 = 3）和后序遍历数组的{6, 7, 3}（从idx + 1 = 3开始，长度为postorderSize - 2 - idx = 7 - 2 - 2 = 3）来构建以3为根节点的右子树。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize) {
// 如果先序遍历数组大小为0，说明没有节点，返回空指针，表示空树
if (preorderSize == 0) {
return NULL;
}
// 为根节点分配内存空间
struct TreeNode *root = malloc(sizeof(struct TreeNode));
// 设置根节点的值为先序遍历数组的第一个元素
// 因为先序遍历的顺序是根节点、左子树、右子树，所以第一个元素就是根节点的值
root->val = preorder[0];
// 初始化根节点的左子树指针为空
root->left = NULL;
// 初始化根节点的右子树指针为空
root->right = NULL;
// 如果先序遍历数组大小大于1，说明除了根节点还有其他节点，需要进一步构建子树
if (preorderSize > 1) {
int idx;
// 遍历后序遍历数组，找到先序遍历数组中第二个元素（即根节点的左子树的根节点在先序遍历中的值）
// 在后序遍历数组中的位置
// 因为后序遍历的顺序是左子树、右子树、根节点，所以先序遍历的第二个元素一定在左子树的后序遍历结果中
for (int i = 0; i < postorderSize; i++) {
if (postorder[i] == preorder[1]) {
idx = i;
break;
}
}
// 递归构建根节点的左子树
// 先序遍历数组从第二个元素开始，长度为idx + 1
// 后序遍历数组从开头开始，长度为idx + 1
root->left = constructFromPrePost(preorder + 1, idx + 1, postorder, idx + 1);
// 如果idx + 2小于先序遍历数组大小，说明存在右子树，需要递归构建右子树
if (idx + 2 < preorderSize) {
// 先序遍历数组从idx + 2开始，长度为先序遍历数组大小减去2再减去idx
// 后序遍历数组从idx + 1开始，长度为后序遍历数组大小减去2再减去idx
root->right = constructFromPrePost(preorder + idx + 2, preorderSize - 2 - idx, postorder + idx + 1, postorderSize - 2 - idx);
}
}
// 返回构建好的根节点指针，通过这个指针可以访问整个构建好的二叉树
return root;
}