已知兩種遍曆序列構造二叉樹

二叉樹的前序遍曆順序是：先訪問根節點，然後前序遍曆左子樹，再前序遍曆右子樹。

中序遍曆順序是：中序遍曆根節點的左子樹，然後是訪問根節點，最後中序遍曆右子樹。

後序遍曆順序是：後續遍曆根節點的左子樹，然後是後序遍曆右子樹，最後訪問根節點。

一，已知前，中序遍曆序列構造二叉樹

 【主要思路】
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);
}