【题解】ACMOJ 1049 前序中序求二叉树

题目描述

ACMOJ - 1049 - 前序中序求二叉树

给定二叉树的前序遍历和中序遍历，将二叉树以数组形式输出

保证节点个数 $n\leq 26$，且输出长度 $k\leq 10^3$

问题分析

这是一个经典的二叉树问题，我们使用递归的方法求解：

• 选取前序遍历的第一个节点作为子树根节点
• 在中序遍历中找到该节点的位置，其左侧构成左子树，右侧构成右子树
• 将前序遍历相应地分成两棵子树，分别递归地重复上述过程

由于递归深度不超过 $n$，每层子问题的规模之和也不超过 $n$，因此时间复杂度为 $O(n^2)$

一些细节

1. 注意数组开够大小，避免越界
2. 注意递归的边界条件和参数传递准确无误

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

char pre[35], mid[35], val[1005];
int len, cnt = 0;

void find(int pre_left, int pre_right, int mid_left, int mid_right, int order)
{
    if (mid_left > mid_right)
        return;
    val[order] = pre[pre_left], cnt = std::max(cnt, order);
    int root = mid_left;
    while (root <= mid_right && mid[root] != pre[pre_left])
        root++;
    find(pre_left + 1, pre_left + root - mid_left, mid_left, root - 1, order << 1);
    find(pre_left + root - mid_left + 1, pre_right, root + 1, mid_right, order << 1 | 1);
}

int main()
{
    scanf("%s%s", pre, mid), len = strlen(pre);
    find(0, len - 1, 0, len - 1, 1);
    for (int i = 1; i <= cnt; i++)
        if (val[i])
            printf("%c ", val[i]);
        else
            printf("NULL ");
    return 0;
}