洛谷 P1030 求先序排列 题解

发表于 | 分类于 | | 热度: ℃

Description

给出一棵二叉树的中序与后序排列。求出它的先序排列（树结点用不同的大写字母表示）。

数据范围：长度 $≤8$

Solution

做法

中序遍历：ACGDBHZKX；后序遍历：CDGAHXKZB

根据后序遍历的性质，首先可以找到主根 B，输出。找到中序遍历中的 B，可以把整棵树分为 ACGD 和 HZKX；对应的后序遍历为 CDGA 和 HXKZ，分别递归。递归到中序遍历的长度 $=0$ 为止。

实现

a.substr(0, k) 为截取并复制字符串 $a$ 中 $0$ 开始长度为 $k$ 的子串。
a.substr(k) 为截取字符串 $a$ 从 $k$ 开始一直到最后的子串。
a.find(c) 返回字符串 $a$ 中第一个找到字符串 $c$ 的位置。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

string s1, s2;

void dfs(string a, string b)
{
    if(a.size() > 0)
    {
        char c = b[b.size() - 1];
        int k = a.find(c);
        cout << c;
        dfs(a.substr(0, k), b.substr(0, k));
        dfs(a.substr(k + 1, a.size() - k), b.substr(k, b.size() - k - 1));
    }
}

int main()
{
    cin >> s1 >> s2;
    dfs(s1, s2);
    return 0;
}