已知两种遍历序列构造二叉树

二叉树的前序遍历顺序是：先访问根节点，然后前序遍历左子树，再前序遍历右子树。

中序遍历顺序是：中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。

后序遍历顺序是：后续遍历根节点的左子树，然后是后序遍历右子树，最后访问根节点。

一，已知前，中序遍历序列构造二叉树

 【主要思路】
1.通过前序遍历，得知根
2.通过中序遍历，得知左子树的长度。
3.就剩下右子树的未知的，就用递归构建

//辅助函数
struct TreeNode* build(int* preorder, int l1, int r1, int* inorder, int l2, int r2){
    if (l1 > r1) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[l1]; //前序遍历告诉了根在哪里
    int mid = l2;
    while (inorder[mid] != root->val) mid++;
    int leftSize = mid - l2; //中序遍历告诉了左子树的长度（在根之前就是了）
    //递归构建
    root->left = build(preorder, l1 + 1, l1 + leftSize, inorder, l2, mid - 1);
    root->right = build(preorder, l1 + leftSize + 1, r1, inorder, mid + 1, r2);
    return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    return build(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1)   ;
}

二，已知中，后序遍历序列构造二叉树​

【主要思路】
1.关键是想清楚后序遍历如何表示左子树、右子树、根
·前序遍历：根/左子树/右子树 -> 根在头
·中序遍历：左子树/根/右子树 -> 左子树的长度
·后序遍历：左子树/右子树/根 -> 根在尾

其中的关系：
用中序遍历定出左子树的长度： leftSize = left_in - mid
前序preorder 中序inorder 后序postorder
左子树 (left_pr + 1, left_pr + leftSize) || (left_in, mid - 1) || (left_po, left_po + leftSize - 1)
右子树 (left_pr + leftSize + 1, right_pr) || (mid + 1, right_in) || (po + leftSize, right_po - 1)

*mid因为是在中序遍历中诞生的，只能在中序遍历中使用
*为什么后序遍历中的左子树要 - 1？ 因为这是从“0”开始数的数组，其下标是要“ - 1”
*由此可以推论出前序遍历中的左子树不用 - 1。 因为前序遍历的头是根，使得成为“从1开始”的数组

//辅助函数
struct TreeNode* build(int* inorder, int left_in, int right_in, int* postorder, int left_po, int right_po) {
    if (left_in > right_in) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = postorder[right_po];
    int mid = left_in;
    while (inorder[mid] != root->val) mid++;
    int leftSize = mid - left_in;
    root->left = build(inorder, left_in, mid - 1, postorder, left_po, left_po + leftSize - 1);
    root->right = build(inorder, mid + 1, right_in, postorder, left_po + leftSize, right_po - 1);
    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    return build(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1);
}

三，已知前，后序遍历序列构造二叉树

【主要思路】
1.先把根建好，然后算出左子树的长度，把左子树给建好，最后就是右子树。整个过程可以用递归来实现
2.最终的根很好找，就是前序遍历的第一个。
3.左子树的长度怎么算？可以根据前序遍历和后序遍历的定义，即前序：根->左->右，后序：左->右->根，设mid指针在后序遍历上依次移动，等到mid对应的值等于在前序遍历上根的值，这时的mid减去遍历开始位置的下标再加1，就得到左子树的长度
4.得到了左子树的长度，再除了根，剩下的都是右子树

【注意细节】
1.留意特殊情况，比如前序遍历就只有一个节点
2.用C语言建立节点时，记得要初始化。比如建立了一个root点，记得root->left = NULL, root->right = NULL

//辅助函数
struct TreeNode* build(int* preorder, int left_pr, int right_pr, int* postorder, int left_po, int right_po) {
    if (left_pr > right_pr) return NULL; 不能省的特殊情况判断①
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //C语言建立节点方法
    root->val = preorder[left_pr]; 
    root->left = NULL, root->right = NULL; //初始化root节点，省略了这步会报错
    if (left_pr == right_pr) return root; //不能省的特殊情况判断②
    int mid = left_po;
    while (mid < right_po && postorder[mid] != preorder[left_pr + 1]) mid++;
    int leftSize = mid - left_po + 1; //得出左子树长度
    //递归构建左右子树
    root->left = build(preorder, left_pr + 1, left_pr + leftSize, postorder, left_po, mid);
    root->right = build(preorder, left_pr + leftSize + 1, right_pr, postorder, mid + 1, right_po - 1);
    return root;
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize){
    return build(preorder, 0, preorderSize - 1, postorder, 0, postorderSize - 1);
}