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