二叉树输出(btout)

形式化题目

输入两行字符串，分别是一棵二叉树（字符互不重复）的先序和中序序列。按凹入表示法输出这棵树：按先序，每个结点占一行，该行由它的字符重复「结点长度」次，行数等于结点数；叶结点长度为 $1$ ，非叶结点长度等于左右子树长度之和，即长度等于子树中的叶子数。样例输入 ABCDEFG 与 CBDAFEG，样例输出依次为 AAAA、BB、C、D、EE、F、G。

解法总览

两种解法共用同一条观察：先序首字符是根，它在中序里的位置把左右子树切开。差别在「长度（子树叶子数）什么时候算」——递归直接输出时现算，建树时顺手算进结点里。

	解法一：区间递归直接输出（原实现）	解法二：先建树再输出（正式主解）
做法	`walk()` 按先序往下走，走到一个子树就先现算它的叶子数，输出「字符 × 长度」	`build()` 建出 `Node{val, lch, rch, len}`，长度在建树时算好，`walk(root)` 只负责输出
长度来源	单独一个 `length()` 递归（Python 加 `@cache` 记忆化）	`node[u].len`，叶子 1、非叶左右之和
时间	C++ 版每结点现算 O(子树大小)，链状最坏 O(n²)；Python 版记忆化后 O(n)	pos 表 O(1) 定位，建树与输出都是 O(n)
代码	`direct.py` / `direct.cpp`	`main.py` / `main.cpp`

正式主解是 main.py / main.cpp。

解法一：区间递归直接输出

思路

先序首字符是根，它在中序序列中的位置把左右子树切开，递归下去就能还原整棵树；空子树叶子数记 $0$ ，于是 $n \leqslant 1$ 时长度就是 $0/1$ ，只有一个孩子的结点无需分情况讨论。先求出每个结点的长度（子树叶子数），再按先序输出「字符 × 长度」。

代码

Python 版（原实现，length() 用 @cache 记忆化，每个区间只算一次）：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/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-09-30 07:15
# update_at: 2026-10-12 15:05
# direct.py：原方法——区间/子串递归直接产出，不显式建结点树（对比新方法见 main.py）。

# 二叉树的凹入表示法：先序 + 中序区间递归，不显式建结点。
# 先序 [pl, pl+n) / 中序 [il, il+n) 就是一棵子树，先序首字符是根，
# 根在中序中的位置把左右子树切开；结点「长度」= 子树叶子数。
# 如何使用：
# 1. read_input()       # 读入先序、中序，建好 pos 表（字符 -> 中序下标）
# 2. walk(0, 0, len)    # 按先序把「字符 × 长度」逐行写进 out
# 3. solve()            # 装配：读入 -> 递归 -> 输出

import sys
from functools import cache

pre = ""                  # 先序遍历序列
ino = ""                  # 中序遍历序列
pos: dict[str, int] = {}  # pos[c] = 字符 c 在中序中的下标
out: list[str] = []       # 输出的每一行


def read_input() -> None:
    """读入先序、中序序列，建好中序下标表。"""
    global pre, ino, pos
    data = iter(sys.stdin.buffer.read().split())
    pre = next(data).decode()
    ino = next(data).decode()
    pos = {c: i for i, c in enumerate(ino)}  # 字符互不重复，中序下标就是唯一切分点


@cache
def length(pl: int, il: int, n: int) -> int:
    """先序 [pl, pl+n) / 中序 [il, il+n) 这棵子树的根的长度。

    长度等于子树里的叶子数：叶为 1，否则左右之和；空子树记 0，
    于是「只有一个孩子」不必分情况，缺失的那侧自然贡献 0。
    """
    if n <= 1:
        return n                              # n == 0 是空子树，n == 1 是叶
    left_n = pos[pre[pl]] - il                # 根在中序的位置 → 左子树大小
    return length(pl + 1, il, left_n) + length(pl + 1 + left_n, pos[pre[pl]] + 1, n - 1 - left_n)


def walk(pl: int, il: int, n: int) -> None:
    """按先序产出整棵子树：先根自己的那一行，再左子树、右子树。"""
    if n == 0:
        return
    left_n = pos[pre[pl]] - il
    out.append(pre[pl] * length(pl, il, n))   # 该结点字母重复「长度」次
    walk(pl + 1, il, left_n)
    walk(pl + 1 + left_n, pos[pre[pl]] + 1, n - 1 - left_n)


def solve() -> None:
    read_input()
    walk(0, 0, len(pre))
    print('\n'.join(out))


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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * 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-05 12:08
 * update_at: 2026-10-05 12:08
 */
// direct.cpp：原方法——先序/中序区间递归直接输出，不显式建结点树（对比新方法见 main.cpp）。
#include <cstdio>

typedef long long ll;

const int MAXN = 100005; // 结点数上限（题面未给，取足够大）

char buf[MAXN];   // 读入缓冲
int pre[MAXN];    // 先序序列，存字符编码
int ino[MAXN];    // 中序序列，存字符编码
int pos[256];     // pos[字符编码] = 该字符在中序序列中的下标，用于 O(1) 定位切分点
int n;            // 结点个数

// 返回先序 [pl, pl+cnt) 与中序 [il, il+cnt) 这棵子树的叶子数。
// 题面中结点的「长度」就等于子树的叶子数：叶为 1，非叶为左右之和。
// 空子树（cnt == 0）返回 0，于是只有一个孩子时缺失的那侧自然贡献 0。
int leaf_count(int pl, int il, int cnt) {
    if (cnt <= 1) {
        return cnt;
    }
    int left_cnt = pos[pre[pl]] - il; // 先序首字符是根，它在中序中的位置给出左子树大小
    return leaf_count(pl + 1, il, left_cnt)
         + leaf_count(pl + 1 + left_cnt, il + left_cnt + 1, cnt - 1 - left_cnt);
}

// 按先序输出这棵子树：先输出根那一行（字符重复「叶子数」次），再递归左右子树。
void walk(int pl, int il, int cnt) {
    if (cnt == 0) {
        return;
    }
    int line_cnt = leaf_count(pl, il, cnt); // 该结点字符要重复的次数
    for (int i = 0; i < line_cnt; i++) {
        putchar(pre[pl]);
    }
    putchar('\n');
    int left_cnt = pos[pre[pl]] - il; // 左子树大小
    walk(pl + 1, il, left_cnt);
    walk(pl + 1 + left_cnt, il + left_cnt + 1, cnt - 1 - left_cnt);
}

int main() {
    scanf("%s", buf);
    n = 0;
    while (buf[n] != '\0') {
        pre[n] = buf[n];
        n++;
    }
    scanf("%s", buf);
    for (int i = 0; i < n; i++) {
        ino[i] = buf[i];
        pos[ino[i]] = i;
    }

    walk(0, 0, n);
    return 0;
}

复杂度

时间：Python 版每个 (先序起点, 中序起点, 区间长) 只算一次，O(n)；C++ 版没有记忆化，每输出一个结点就重算一次它的子树叶子数，链状最坏 O(n²)、平衡时 O(n log n)，实测数据可过。
空间：递归栈 O(树高)。

解法二：先建树再输出

思路

观察相同，区别在于先序 + 中序还原这棵树时就把长度算好：build(pl, il, cnt) 用先序首字符定根、pos[] O(1) 定位切分点，递归接上左右孩子；叶子长度置 1，非叶取左右之和——长度与结点同时诞生，后面 walk(root) 只需按先序输出「字符 × len」，一次遍历，不必回头重算。

结点的字符、左儿子、右儿子、长度收进同一个 Node，编号即下标（静态数组 + node_cnt 动态开点）。

代码

Python 版：