求先序遍历

题目描述

给定一棵二叉树的中序遍历与后序遍历（结点为互不相同的大写字母，长度 $\le 8$ ），求先序遍历。

输入共两行，第一行为中序遍历，第二行为后序遍历。输出一行先序遍历。

样例：中序 BADC、后序 BDCA，输出 ABCD。

思路

后序最后一个字符是当前子树的根；在中序中找到该根，左边即左子树、右边即右子树。递归输出根、左子树、右子树即得先序。空子树直接返回。

参考代码

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#!/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-10-02 04:19
# update_at: 2026-10-02 04:19

import sys


def preorder(inorder: str, postorder: str) -> str:
    """由中序 + 后序还原先序：后序末位是根，中序按根切成左右子树递归。"""
    if not postorder:  # 空子树
        return ''
    root = postorder[-1]                       # 后序最后一个一定是子树根
    i = inorder.index(root)                    # 根在中序里的位置 = 左子树大小
    left, right = i, len(inorder) - i - 1
    return root + preorder(inorder[:left], postorder[:left]) \
        + preorder(inorder[left + 1:], postorder[left:left + right])


def solve() -> None:
    data = iter(sys.stdin.read().split())
    inorder, postorder = next(data), next(data)
    print(preorder(inorder, postorder))


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/**
 * 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 12:15
 * update_at: 2026-10-06 12:15
 */
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

string inorder, postorder;

// 由中序区间 [l1, r1] 与后序区间 [l2, r2] 递归输出先序
void preorder(ll l1, ll r1, ll l2, ll r2) {
    if (l1 > r1 || l2 > r2) return; // 空子树
    char root = postorder[r2];      // 后序末位是根
    cout << root;
    ll i = l1;
    while (i <= r1 && inorder[i] != root) ++i; // 根在中序中的位置
    ll left_size = i - l1;          // 左子树结点个数
    // 左子树：中序 [l1, i-1]，后序 [l2, l2+left_size-1]
    preorder(l1, i - 1, l2, l2 + left_size - 1);
    // 右子树：中序 [i+1, r1]，后序 [l2+left_size, r2-1]
    preorder(i + 1, r1, l2 + left_size, r2 - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> inorder >> postorder;
    ll n = inorder.size();
    preorder(0, n - 1, 0, n - 1);
    cout << '\n';
    return 0;
}

目录

题目描述

思路

参考代码