P1827. 美国血统

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 389 阅读时长 ≈ 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 pre, 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 (pre[pl] == in[idx])
        {
            dfs(pl + 1, pl + idx - il, il, idx - 1);//递归左子树
            dfs(pl + idx - il + 1, pr, idx + 1, ir);//递归右子树
            cout << pre[pl];//输出当前根结点
        }
    }
}

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

思路

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

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

假设有：

  • 前序遍历 {1 2 3 4 5 6 7}
  • 中序遍历 {4 3 5 2 6 1 7}

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

  • 前序遍历 {[1] 2 3 4 5 6 7}

  • 中序遍历 {4 3 5 2 6 [1] 7}

所以“4 3 5 2 6”这些数都是在以1为根的左子树里面，“7”是在以1为根的右子树里面

因此，可以在前序遍历中提取出“2 3 4 5 6”这个区间作为左子树的前序遍历，“7”这个区间作为右子树的前序遍历

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