前序和后序遍历

如果只有先序遍历和后序遍历，生成出来的树是不唯一的。比如 1234 和 2431 ，生成出来的树中4可能是左子树也可能是右子树。但是如果有中序遍历的结果就不一样，就可以确定是左子树还是右子树。

• 因为这题的数据范围非常小，因此可以直接暴力搜，枚举所有方案判断方案的合法性。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>

using namespace std;

const int N = 40;
int n;
int pre[N], post[N];

int dfs(int prel, int prer, int postl, int postr, string &in)
{
  if (prel > prer) return 1;
  if (pre[prel] != post[postr]) return 0;

  int cnt = 0;
  for (int i = prel; i <= prer; i ++ )
  {
      string inl, inr;
      int cntl = 0, cntr = 0;
      cntl = dfs(prel + 1, i, postl, postl + i - prel - 1, inl);
      cntr = dfs(i + 1, prer, postl + i - prel - 1 + 1, postr - 1, inr);

      if (cntl == 0 || cntr == 0) continue;

      cnt += cntl * cntr;
      in = inl + to_string(pre[prel]) + " " + inr;
      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 in;
  int ct = dfs(0, n - 1, 0, n - 1, in);

  if (ct > 1) puts("No");
  else puts("Yes");

  in.pop_back();
  cout << in << endl;

  return 0;
}