Go(1.14.4) 解法, 执行用时: 303ms, 内存消耗: 15016K, 提交时间: 2020-08-07 00:03:32

package main

// github.com/EndlessCheng/codeforces-go
func solve(n int, pre []int, suf []int) []int {
	ans := []int{}
	p := make([]int, n+1)
	for i, v := range suf {
		p[v] = i
	}
	var f func(pl, pr, sl, sr int)
	f = func(pl, pr, sl, sr int) {
		l := 0
		if pl < pr {
			l = p[pre[pl+1]] - sl + 1
			f(pl+1, pl+l, sl, sl+l-1)
		}
		ans = append(ans, pre[pl])
		if l+1 < pr-pl+1 {
			f(pl+l+1, pr, sl+l, sr)
		}
	}
	f(0, n-1, 0, n-1)
	return ans
}

Python3 解法, 执行用时: 384ms, 内存消耗: 41756K, 提交时间: 2022-04-16 12:04:37

import sys
sys.setrecursionlimit(100005)
class Solution:
    def solve(self , n , pre , suf ):
        def dfs(pre,suf):
            if not pre:return []
            if len(pre)==1:return [pre[0]]
            root=[pre[0]]
            index=suf.index(pre[1])
            left=dfs(pre[1:2+index],suf[:index+1])
            right=dfs(pre[2+index:],suf[index+1:-1])
            return left+root+right
        ans= dfs(pre,suf)
        return ans

C++11(clang++ 3.9) 解法, 执行用时: 66ms, 内存消耗: 6364K, 提交时间: 2020-08-07 20:13:06

class Solution {
public:
vector<int> ans,c,d;
int m[100005];
void find(int l,int r,int x,int y){
	if(l>r)return;
	if(l==r){ans.push_back(c[l]);return;}
	int p=m[c[l+1]],len=y-p-1;
	find(l+1,r-len,x,y-len-1);
	ans.push_back(c[l]);
	find(r-len+1,r,y-len,y-1);
}
vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
    c=pre,d=suf;
	for(int i=0;i<n;++i)m[suf[i]]=i;
	find(0,n-1,0,n-1);
	return ans;
}
};