fork download
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int n;
  6. int in[100000], post[100000];
  7.  
  8. void func(int is, int ie, int ps, int pe) {
  9. if(is >= ie || ps >= pe)
  10. return;
  11.  
  12. int root = post[pe-1];
  13. int ri = find(in+is, in+ie, root)-in;
  14. cout << root << " ";
  15.  
  16. int ln = ri-is;
  17.  
  18. func(is, ri, ps, ps+ln);
  19. func(ri+1, ie, ps+ln, pe-1);
  20. }
  21.  
  22. int main() {
  23. ios::sync_with_stdio(false);
  24. cin.tie(NULL);
  25. cout.tie(NULL);
  26. cin >> n;
  27.  
  28. //인 오더
  29. //포스트 오더
  30. for(int i = 0; i < n; i++)
  31. cin >> in[i];
  32. for(int i = 0; i < n; i++)
  33. cin >> post[i];
  34.  
  35. //포스트 오더의 맨 뒤가 루트
  36. //=> 인오더에서 루트의 좌 우가
  37. func(0, n, 0, n);
  38.  
  39. return 0;
  40. }
Success #stdin #stdout 0s 5304KB
stdin
3
1 2 3
1 3 2
stdout
2 1 3