根据二叉树的先、中序列构建一颗二叉树，输出该二叉后序序列

 题目：根据二叉树的先序序列和中序序列构建一颗二叉树，并输出该二叉树的后序序列。

【问题描述】根据二叉树的先序序列和中序序列构建一颗二叉树，并输出该二叉树的后序序列。

【输入形式】二叉树的先序序列

           二叉树的中序序列

【输出形式】二叉树的后序序列

【样例输入】A B C D

           B D C A

【样例输出】D C B A

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }
    
    // 创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preorder[preStart];
    root->left = NULL;
    root->right = NULL;
    
    // 在中序遍历中找到根节点的位置
    int i;
    for (i = inStart; i <= inEnd; i++) {
        if (inorder[i] == preorder[preStart]) {
            break;
        }
    }
    int leftLen = i - inStart; // 左子树的长度
    
    // 递归构建左右子树
    root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftLen, inStart, i - 1);
    root->right = buildTree(preorder, inorder, preStart + leftLen + 1, preEnd, i + 1, inEnd);
    
    return root;
}

// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%c ", root->val);
}

int main() {
    char preorder[100];
    char inorder[100];
    scanf("%s", preorder); // 输入前序遍历序列
    scanf("%s", inorder); // 输入中序遍历序列
    
    TreeNode* root = buildTree(preorder, inorder, 0, strlen(preorder) - 1, 0, strlen(inorder) - 1);
    
    printf("后序序列：");
    postorderTraversal(root);
    printf("\n");
    
    return 0;
}