usaco-3.4.2 美国血统

题目描述

给定一棵二叉树的中序遍历序列与前序遍历序列，节点用唯一的大写字母表示（ $n \le 26$ ），求其后序遍历序列。输入第一行为中序遍历，第二行为同一棵树的前序遍历；输出单独一行后序遍历，如输入 ABEDFCHG 与 CBADEFGH 时输出 AEFDBHGC。

思路

前序序列的第一个字符就是根节点；由于节点字母唯一，在中序序列中找到根的位置，左边是左子树、右边是右子树，且左子树长度已知，可在前序中同样切分出左右子树的前序序列。按「递归左子树、递归右子树、输出根」的顺序分治即可直接打印后序遍历，无需显式建树。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-10-04 13:02
import sys


def post_order(inorder: str, preorder: str) -> str:
    """由中序与前序构造后序遍历字符串：左子树后序 + 右子树后序 + 根。"""
    if not preorder:
        return ""
    root = preorder[0]
    mid = inorder.index(root)
    left_post = post_order(inorder[:mid], preorder[1 : 1 + mid])
    right_post = post_order(inorder[mid + 1 :], preorder[1 + mid :])
    return f"{left_post}{right_post}{root}"


def solve() -> None:
    # 空格分隔的输入：先顺序消费中序，再消费前序，两个位置量各自有名字
    data = iter(sys.stdin.buffer.read().decode().split())
    inorder = next(data, None)
    if inorder is None:  # 空输入防御：没有任何 token 就直接返回
        return
    preorder = next(data)
    print(post_order(inorder, preorder))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:36
 * update_at: 2026-10-06 10:36
 */
#include <cstdio>
#include <string>
#include <iostream>

typedef long long ll;

using std::string;

string inorder_str;  // 中序遍历序列
string preorder_str; // 前序遍历序列

// 递归输出后序遍历：左子树 -> 右子树 -> 根
// l1, r1 是当前中序序列的区间，l2, r2 是当前前序序列的区间（闭区间）
void dfs(ll l1, ll r1, ll l2, ll r2) {
    if (l1 > r1) return; // 空子树

    // 前序的第一个字符就是当前子树的根
    char root = preorder_str[l2];

    // 节点字母唯一，在中序中找根的位置，左边是左子树，右边是右子树
    ll mid = l1;
    while (inorder_str[mid] != root) mid++;

    ll left_len = mid - l1; // 左子树节点个数

    dfs(l1, mid - 1, l2 + 1, l2 + left_len);              // 先递归左子树
    dfs(mid + 1, r1, l2 + left_len + 1, r2);              // 再递归右子树
    std::cout << root;                                    // 最后输出根
}

int main() {
    std::cin >> inorder_str >> preorder_str;
    ll n = inorder_str.size();

    dfs(0, n - 1, 0, n - 1);
    std::cout << "\n";
    return 0;
}

usaco-3.4.2 美国血统

目录

题目描述

思路

参考代码