【PTA数据结构 | C语言版】根据后序和中序遍历输出前序遍历

本专栏持续输出数据结构题目集，欢迎订阅。

题目

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的前序遍历结果。

输入格式:
第一行给出正整数 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 30

int 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;
}