背景（NJU 19年保研机试题）

每一个上过数据结构课的人都知道，我们不一定可以通过前序遍历和后序遍历唯一地确定一棵树——不过，我们能够算出来有多少种可能的方案吗？

思路

前序遍历对原树是如下的划分：

[root] [left] [right]

后序遍历是类似的：

[left] [right] [root]

但是，可能存在如下情况：

前序：1 2 3

后序：3 2 1

我们只能确定2 3在同一棵子树中，但是我们无法确定他们在那一棵子树中，这就是前、后序遍历无法确定子树的情况。当出现该情况时， 当前子树的可能构型为子树的可能构型*2；对于有两棵子树的，当前子树的构型为其左右子树构型数量的积。

实现

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
39
#include <bits/stdc++.h>
using namespace std;


int dfs(const vector<int>& pre, int l1, int r1, const vector<int>& post, int l2, int r2){
    if(l1>r1 || l2>r2){
        return 1;
    }

    int root_ind = find(pre.begin(), pre.end(), post[r2])-pre.begin();
    
    if(l1==r1){
        return 1;
    }else{
        int left_ind = find(post.begin(), post.end(), pre[l1+1])-post.begin();
        if(left_ind == r2-1){
            return dfs(pre, l1+1, r1, post, l2, r2-1)*2;
        }else{
            return dfs(pre, l1+1, l1+1+left_ind-l2, post, l2, left_ind) * dfs(pre, l1+2+left_ind-l2, r1, post, left_ind+1, r2-1);
        }
    }
}

int main(){
    int n;
    cin>>n;

    vector<int> pre(n), post(n);
    for(int i =0;i<n;i++){
        cin>>pre[i];
    }

    for(int i = 0;i<n;i++){
        cin>>post[i];
    }

    cout<<dfs(pre, 0, n-1, post, 0, n-1);
    return 0;
}