本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

本題要求根據給定的一棵二叉樹的后序遍歷和中序遍歷結果，輸出該樹的前序遍歷結果。

輸入格式:
第一行給出正整數 n (≤30)，是樹中結點的個數。隨后兩行，每行給出 n 個整數，分別對應后序遍歷和中序遍歷結果，數字間以空格分隔。題目保證輸入正確對應一棵二叉樹。

輸出格式:
在一行中輸出Preorder: 以及該樹的前序遍歷結果。數字間有1個空格，行末不得有多余空格。

輸入樣例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

輸出樣例:
Preorder: 4 1 3 2 6 5 7

代碼

#include <stdio.h>
#include <stdlib.h>#define MAX_N 30int postorder[MAX_N], inorder[MAX_N];
int first_output = 1; // 標記是否是第一個輸出的節點// 根據后序和中序遞歸構建二叉樹并輸出前序遍歷
void buildAndPrintPre(int post_start, int post_end, int in_start, int in_end) {if (post_start > post_end || in_start > in_end) return;// 后序遍歷的最后一個元素是根節點int root_val = postorder[post_end];// 控制輸出格式if (first_output) {printf("Preorder: %d", root_val);first_output = 0;} else {printf(" %d", root_val);}// 在中序遍歷中找到根節點的位置int root_pos = in_start;while (inorder[root_pos] != root_val) root_pos++;// 計算左子樹的節點數int left_count = root_pos - in_start;// 遞歸處理左子樹buildAndPrintPre(post_start, post_start + left_count - 1, in_start, root_pos - 1);// 遞歸處理右子樹buildAndPrintPre(post_start + left_count, post_end - 1, root_pos + 1, in_end);
}int main() {int n;scanf("%d", &n);// 讀取后序遍歷for (int i = 0; i < n; i++) {scanf("%d", &postorder[i]);}// 讀取中序遍歷for (int i = 0; i < n; i++) {scanf("%d", &inorder[i]);}// 構建并輸出前序遍歷buildAndPrintPre(0, n - 1, 0, n - 1);printf("\n");return 0;
}