P1030. 求先序排列

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 388 阅读时长 ≈ 1 分钟

考点

  • 二叉树

题解

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
#include <bits/stdc++.h>
using namespace std;
//后序排列与中序排列
string post, in;

//pl: 后序排列左端点
//pr: 后序排列右端点
//il: 中序排列左端点
//ir: 中序排列右端点
void dfs(int pl, int pr, int il, int ir)
{
    if (pr < pl || ir < il)
        return;
    for (int idx = il; idx <= ir; ++idx)
    {
        if (post[pr] == in[idx])
        {
            cout << in[idx];//输出当前根结点
            dfs(pl, pl + idx - il - 1, il, il + idx - 1);//递归左子树
            dfs(pl + idx - il, pr - 1, idx + 1, ir);//递归右子树
        }
    }
}

int main()
{
    cin >> in >> post;
    dfs(0, post.length() - 1, 0, in.length());
    return 0;
}

思路

通过后序遍历可以找出当前二叉树的根（即后序遍历中最后一个位置的值）

中序遍历可以找出当前二叉树的根所在的位置，即可以找到左子树与右子树的大小；即可递归找左右子树的根结点

假设有：

  • 后序遍历 {D E B C A}
  • 中序遍历 {D B E A C}

先找出后序遍历的根A，然后在中序遍历中找到A的位置

  • 后序遍历 {D E B C [A]}
  • 中序遍历 {D B E [A] C}

所以“D B E”这些数都是在以A为根的左子树里面，“C”是在以A为根的右子树里面

因此，可以在后序遍历中提取出“D E B”这个区间作为左子树的后序遍历，“C”这个区间作为右子树的后序遍历

最终递归的时候按照前序遍历的顺序输出根结点的值即可