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