输入格式: 两行。第一行是二叉树的前序遍历序列，第二行是中序遍历序列。每个数字表示的结点之间用空格隔开。 输出格式： 一行。由输入中的前序列和中序遍历序列重建的二叉树的后序遍历序列。每个数字表示的结点之间用空格隔开

算法思路：
因为前序遍历的第一个结点必然是根结点，根据这个结点可以将中序遍历序列划分为左子树和右子树两个部分。递归进行这个过程，直到子树中只有一个结点。因为递归过程中每一步都是将根结点移到最后访问，所以最后输出的就是后序遍历序列。
Python代码：

相关问题

C语言交换二叉树中每个结点的左孩子和右孩子，输出有两行：第一行是原二叉树的中序遍历序列，第二行是交换后的二叉树的中序遍历序列

假设二叉树的结点类型为：
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

交换二叉树中每个结点的左孩子和右孩子的操作可以通过递归实现：
void swap(TreeNode *root) {
if (root == NULL) {
return;
}
swap(root->left);
swap(root->right);
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
}

在交换完二叉树后，输出原二叉树和交换后的二叉树的中序遍历序列可以使用递归实现：
void inorder(TreeNode *root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}

int main() {
// 构建二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = NULL;

// 输出原二叉树中序遍历序列
inorder(root);
printf("\n");

// 交换二叉树中每个结点的左孩子和右孩子
swap(root);

// 输出交换后的二叉树中序遍历序列
inorder(root);
printf("\n");

return 0;
}

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔c语言

在C语言中，你可以使用递归的方式来解析二叉树的中序和前序遍历序列，然后重构出二叉树结构。这里是一个简单的步骤描述：

数据结构定义：
首先，需要定义一个二叉树节点的数据结构，包含一个整数值val和两个指向左右子节点的指针left和right。

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

函数实现：
创建根节点：根据给定的第一个元素创建一个新节点作为根节点。
中序遍历：对于输入的中序序列，可以先处理左子树（因为中序遍历先左后根右），找到当前节点的位置，然后递归构建左子树和右子树。
前序遍历：同样对前序序列进行处理，先处理根节点，接着递归处理左子树和右子树。

// 假设输入的中序和前序序列存储在数组in[]和pre[]中
void buildTree(int in[], int pre[], int n) {
TreeNode* root = createNode(pre[0]); // 根据第一个元素创建根节点
TreeNode* temp = root; // 当前访问的节点
for (int i = 1; i < n; ++i) {
if (findInOrder(in, i) == findPreOrder(pre, i)) { // 找到中序和前序相同的节点位置
temp->left = createNode(in[i]);
temp = temp->left;
} else {
temp->right = createNode(in[i]);
temp = temp->right;
}
}
}

// 辅助函数用于创建新节点、查找元素在数组中的位置等
TreeNode* createNode(int val) {...}
int findInOrder(int in[], int n) {...}
int findPreOrder(int pre[], int n) {...}

主函数：
在主程序中，读取输入的n、中序和前序序列，并调用上述函数构建二叉树。

int main() {
int N;
scanf("%d", &N);
int in[N], pre[N];
// 读取并存储输入的序列
... // 读取并分配空间给in[]和pre[]
buildTree(in, pre, N);
// 现在根节点就是重建的二叉树的根
return 0;
}