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. cin >> n;
  24.  
  25. //인 오더
  26. //포스트 오더
  27. for(int i = 0; i < n; i++)
  28. cin >> in[i];
  29. for(int i = 0; i < n; i++)
  30. cin >> post[i];
  31.  
  32. //포스트 오더의 맨 뒤가 루트
  33. //=> 인오더에서 루트의 좌 우가
  34. func(0, n, 0, n);
  35.  
  36. return 0;
  37. }
Success #stdin #stdout 0.01s 5460KB
stdin
3
1 2 3
1 3 2
stdout
2 1 3