层序保证祖先先于子孙：中序区间中层序排名最小的字符就是子树根，递归切分输出先序。
OJ: roj
题目 ID: 1364
难度:入门
标签:入门二叉树树的遍历递归python
创建: 2026-09-30 07:15
更新: 2026-10-12 15:28
形式化题目
给定一棵二叉树的中序遍历和层序遍历字符串（字符互不重复），输出其先序遍历字符串。
输入两行，分别为中序序列和层序序列；输出一行先序序列。例如中序 DBEAC、层序 ABCDE 输出 ABDEC。
解法总览
两种解法建立在同一条关键观察上：层序遍历里祖先一定排在子孙前面，所以任意中序区间对应的子树根，就是该区间里层序名次最小的那个字符。差别只在「要不要把树真的建出来」。
| 解法一：区间递归直接产出（原实现） | 解法二：先建树再遍历（正式主解） | |
|---|---|---|
| 做法 | 边找根、边切区间、边写输出，不保存任何结点 | 先按同一规则建出 Node{val, lch, rch} 结点表，再先序走一遍 |
| 中间结构 | 只有递归栈，O(树高) | 结点表 O(n)，之后想走中序、后序、求深度都不用重算 |
| 时间 | 每层要扫区间找根并定位，最坏 O(n²)（链状时） | 同左，另外加 O(n) 的遍历 |
| 代码 | direct.py / direct.cpp |
main.py / main.cpp |
正式主解是 main.py / main.cpp。
解法一：区间递归直接产出
思路
层序遍历中祖先一定排在子孙前面，所以任意中序区间对应的子树根，就是该区间字符中层序排名最小的那个。先输出根，再按根在中序中的位置切分左右两段递归。
代码
Python 版（原实现）：
python
#!/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:16
# update_at: 2026-10-12 15:05
# direct.py：原方法——区间/子串递归直接产出，不显式建结点树（对比新方法见 main.py）。
# 中序 + 层序还原二叉树并输出先序：区间递归，不显式建结点。
# 一段中序区间 [lo, hi) 就对应一棵子树，根 = 区间里层序名次最小的字符，
# 因为层序遍历中祖先一定排在子孙前面。
# 如何使用：
# 1. read_input() # 读入中序、层序，建好 rank 排名表
# 2. preorder(0, n) # 递归把中序区间 [lo, hi) 对应子树的先序写进 out
# 3. solve() # 装配：读入 -> 递归 -> 输出
import sys
inorder = "" # 中序遍历序列
level = "" # 层序遍历序列
rank: dict[str, int] = {} # rank[c] = 字符 c 在层序中的名次（越小越靠近根）
out: list[str] = [] # 先序序列，按访问顺序收集字符
def read_input() -> None:
"""读入中序、层序序列，建好层序名次表。"""
global inorder, level, rank
data = iter(sys.stdin.buffer.read().split())
inorder = next(data).decode()
level = next(data).decode()
rank = {ch: i for i, ch in enumerate(level)}
def preorder(lo: int, hi: int) -> None:
"""递归把中序区间 [lo, hi) 这棵子树的先序序列写进 out。"""
if lo == hi:
return
# 根 = 层序名次最靠前的区间内字符：层序保证祖先一定排在子孙前面
root = min(inorder[lo:hi], key=rank.__getitem__)
out.append(root)
mid = inorder.index(root, lo, hi) # 根把中序切成左右子树两段
preorder(lo, mid) # 左子树区间 [lo, mid)
preorder(mid + 1, hi) # 右子树区间 [mid+1, hi)
def solve() -> None:
read_input()
preorder(0, len(inorder))
print(''.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:07
* update_at: 2026-10-05 12:07
*/
// direct.cpp：原方法——区间递归直接产出先序序列，不显式建结点树（对比新方法见 main.cpp）。
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // 字符串长度上限
char inorder[MAXN]; // 中序遍历序列
char level[MAXN]; // 层序遍历序列
int rank_pos[MAXN]; // 字符在层序中的排名（字符用下标 0~25 或 ASCII 映射）
char out[MAXN]; // 先序遍历输出序列
int out_len; // 已输出长度
int n; // 序列长度
// 递归输出中序区间 [l, r)（左闭右开）对应的子树的先序序列
void preorder(int l, int r) {
if (l >= r) return; // 空区间
// 根 = 该区间内层序排名最小的字符（层序保证祖先排在子孙前面）
int best = l;
for (int i = l + 1; i < r; i++) {
if (rank_pos[(int)inorder[i]] < rank_pos[(int)inorder[best]]) {
best = i;
}
}
char root = inorder[best];
out[out_len++] = root; // 先序先输出根
// 在中序里定位根的位置，把区间切成左、右子树两段
int mid = l;
while (mid < r && inorder[mid] != root) mid++;
preorder(l, mid); // 左子树 [l, mid)
preorder(mid + 1, r); // 右子树 [mid+1, r)
}
int main() {
scanf("%s %s", inorder + 1, level + 1);
n = strlen(inorder + 1);
// 按层序建立排名表
for (int i = 1; i <= n; i++) {
rank_pos[(int)level[i]] = i;
}
// 因为输入字符串从位置 1 开始，中序区间 [1, n+1)
preorder(1, n + 1);
out[out_len] = '\0';
printf("%s\n", out);
return 0;
}复杂度
- 时间：每层要扫一遍当前区间找根、再定位根的位置，最坏 O(n²)（链状树），平衡时 O(n log n)。
- 空间：只用递归栈，O(树高)。
解法二：先建树再遍历
思路
用的是同一条观察，区别在于先把树存下来：递归不再直接输出，而是 new_node() 开一个结点、把左右孩子接上，返回根编号；建完再从根做一遍先序遍历 preorder(root) 输出。
结点的字符、左儿子、右儿子收进同一个 Node，编号就是下标（动态化静态：静态数组 + node_cnt 当分配指针）。好处是树变成了可复用的中间结构——同一棵树再要中序、后序、深度、叶子数都只需再走一遍，不必重新切分区间。
代码
Python 版：
python
#!/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:16
# update_at: 2026-10-12 15:25
# 新方法：先建出二叉树，再先序遍历输出（原方法「区间递归直接产出」见 direct.py）。
# 树的存储：一个结点的字符、左儿子、右儿子收进 Node，编号即下标。
# 如何使用：
# 1. read_input() # 读入中序、层序，建好层序名次表 rank
# 2. root = build(0, n) # 用中序区间 [lo, hi) 建树，返回根编号
# 3. preorder(root) # 先序遍历把字符写进 out，solve() 负责装配输出
import sys
class Node:
"""编号 u 的结点：字符 + 左右孩子（0 表示空）。"""
def __init__(self) -> None:
self.val = "" # 结点字符
self.lch = 0 # 左儿子编号，0 表示空
self.rch = 0 # 右儿子编号，0 表示空
node: list[Node] = [] # node[u]：编号 u 的结点，下标 0 是占位
node_cnt = 0 # 已分配的结点个数
inorder = "" # 中序遍历序列
level = "" # 层序遍历序列
rank: dict[str, int] = {} # rank[c] = 字符 c 在层序中的名次（越小越靠近根）
out: list[str] = [] # 先序序列，按访问顺序收集字符
def new_node(ch: str) -> int:
"""动态化静态开点：分配一个新结点并返回它的编号。"""
global node_cnt
node_cnt += 1
node.append(Node())
node[node_cnt].val = ch
return node_cnt
def read_input() -> None:
"""读入中序、层序序列，建好层序名次表。"""
global inorder, level, rank, node
data = iter(sys.stdin.buffer.read().split())
inorder = next(data).decode()
level = next(data).decode()
rank = {ch: i for i, ch in enumerate(level)}
node = [Node()] # 下标 0 占位，结点编号从 1 开始
def build(lo: int, hi: int) -> int:
"""用中序区间 [lo, hi) 建树，返回根编号；空区间返回 0。"""
if lo == hi:
return 0
# 根 = 层序名次最靠前的区间内字符：层序保证祖先一定排在子孙前面
root = min(inorder[lo:hi], key=rank.__getitem__)
u = new_node(root)
mid = inorder.index(root, lo, hi) # 根把中序切成左右子树两段
node[u].lch = build(lo, mid) # 根左边一段是左子树
node[u].rch = build(mid + 1, hi) # 根右边一段是右子树
return u
def preorder(u: int) -> None:
"""先序遍历：根 -> 左子树 -> 右子树，把结点字符依次写进 out。"""
if u == 0:
return
out.append(node[u].val)
preorder(node[u].lch)
preorder(node[u].rch)
def solve() -> None:
read_input()
preorder(build(0, len(inorder)))
print("".join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:07
* update_at: 2026-10-12 15:09
*/
// main.cpp：中序 + 层序还原二叉树（动态化静态建结点），再先序遍历输出。
//
// 层序遍历里祖先一定排在子孙前面，所以中序区间内层序名次最小的字符就是子树根：
// 建树时把值、左儿子、右儿子聚合成 struct Node，node[u] 就是编号 u 的结点，
// 根在中序里的位置把区间切成左右两段，递归接上左右儿子，最后先序走一遍。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int maxn = 1005; // 题面未给串长上限；字母互不重复，按原实现开 1005 留足余量
struct Node {
char val; // 结点的字符
int lch; // 左儿子编号，0 表示空
int rch; // 右儿子编号，0 表示空
};
Node node[maxn]; // node[u]：编号 u 的结点（编号按建树顺序分配）
int node_cnt; // 已分配的结点个数
char inorder[maxn]; // 中序遍历序列，下标从 1 开始
char level[maxn]; // 层序遍历序列，下标从 1 开始
int rank_pos[256]; // rank_pos[c] = 字符 c 在层序中的名次，名次越小越靠近根
int n; // 结点个数
// 动态化静态开点：静态数组 + 分配指针 node_cnt，返回新结点的编号
int new_node(char val) {
node_cnt++;
node[node_cnt].val = val;
node[node_cnt].lch = 0;
node[node_cnt].rch = 0;
return node_cnt;
}
// 用中序区间 [l, r] 建树，返回根编号；空区间返回 0
int build(int l, int r) {
if (l > r) {
return 0;
}
// 根 = 区间内层序名次最小的字符：子孙一定排在祖先后面，名次不可能更小
int best = l;
for (int i = l + 1; i <= r; i++) {
if (rank_pos[inorder[i]] < rank_pos[inorder[best]]) {
best = i;
}
}
int u = new_node(inorder[best]);
node[u].lch = build(l, best - 1); // 根左边一段是左子树
node[u].rch = build(best + 1, r); // 根右边一段是右子树
return u;
}
// 先序遍历：根 -> 左子树 -> 右子树，把结点字符依次输出
void preorder(int u) {
if (u == 0) {
return;
}
putchar(node[u].val);
preorder(node[u].lch);
preorder(node[u].rch);
}
int main() {
scanf("%s %s", inorder + 1, level + 1);
n = strlen(inorder + 1);
for (int i = 1; i <= n; i++) {
rank_pos[level[i]] = i; // 名次从 1 数，保证"最小名次"就是最先出现的祖先
}
preorder(build(1, n));
putchar('\n');
return 0;
}复杂度
- 时间：建树 O(n²) 最坏（每层扫区间找根），遍历 O(n)。
- 空间：结点表 O(n)，递归栈 O(树高)。
复杂度对比
| 解法一 | 解法二 | |
|---|---|---|
| 时间 | O(n²) 最坏 | O(n²) 最坏 + O(n) 遍历 |
| 空间 | O(树高) | O(n) 结点表 |
| 能否复用树结构 | 不能 | 能 |
| 适合场景 | 只求一次先序、追求最小内存 | 后续还要在树上做别的事 |
两法时间同阶，选择看目的：一次性输出用解法一，把树当数据结构反复使用用解法二。
总结
- 层序 + 中序还原二叉树的通用套路是「区间内层序名次最小者为根」，这条观察两种解法共用，先想清楚它再决定要不要建树。
- 建树与否是一次存储换复用的权衡：多花 O(n) 结点表，换来的是后续任意遍历、统计都能直接走树。
Node聚合字段 +node_cnt动态开点是这本仓库里建二叉树的标准写法（见《树的存储》）。