1119 Pre- and Post-order Traversals

题目描述
知识点： 树的遍历，爆搜
思路： 由前序遍历和后序遍历可以知道当前根的位置，但是不知道左子树的区间以及右子树的区间。则需要暴力搜索左子树区间起点，然后逐层递归下去。当满足：当前区间的前序遍历根不等于后续遍历的根，则说明当前区间不合法，不能构成一棵树，直接返回0。当左端点区间大于右端点区间说明为空树，方案返回1
递归每次返回该区间能构成树的方案树，然后递归左右子树相乘就得到总的构成方案数。
当枚举过程中发现方案数>1可以提前break剪枝。

说明，为什么枚举的区间端点从左端点开始，而不是左端点+1。因为这样枚举可以枚举到左子树为空的情况，这也是有可能发生的。

#include
using namespace std;
const int N = 35;
int pre[N],post[N],n;
//参数含义：当前区间 前序遍历左端点 前序遍历右端点 后序遍历左端点 后序遍历右端点 当前字符串。
int dfs(int pre_l,int pre_r,int post_l,int post_r,string &cur){
    if(pre_l > pre_r) return 1;
    if(pre[pre_l] != post[post_r]) return 0;
    int cnt = 0;
    for(int i = pre_l;i <= pre_r;i++){//枚举区间
        string left,right;
        int cnt_l = dfs(pre_l+1,i,post_l,post_l+i-pre_l-1,left);
        int cnt_r = dfs(i+1,pre_r,post_l+i-pre_l-1+1,post_r-1,right);
        if(cnt_l*cnt_r){
            cur = left + to_string(pre[pre_l]) + " "+ right;
            cnt += cnt_l * cnt_r;   
            if(cnt > 1)
               break;              
        }          
    }
    return cnt;
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i++) cin>>pre[i];
    for(int i = 0;i < n;i++) cin>>post[i];
    string res = "";
    int cnt = dfs(0,n-1,0,n-1,res);
    if(cnt > 1)
      cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    res.pop_back();
    cout<<res<<endl;
    return 0;
}
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