fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n; //number of elements in a test case
  5. int arr[10000]; // array to store preorder traversal
  6. int ans[10000]; // array to store postorder traversal in reverse order
  7. int k=0; // index in ans[] array
  8. bool ans_no = 0; // this boolean variable will be set if answer does not exist for a test case
  9.  
  10. //  returns,
  11. //  index of an element in array-range [s...e] which is greater than "ele"
  12. //  if not exist then -1
  13. //  also checks for preorder correctness
  14. int indexof(int s, int e, int ele)
  15. {
  16.     int ret=-1;
  17.  
  18.     // finding index
  19.     for(int i=s; i<=e;i++){
  20.         if(arr[i]>ele){
  21.             ret=i;
  22.             break;
  23.         }
  24.     }
  25.  
  26.     if(ret==-1) return ret;
  27.  
  28.     // checking all element in range [s+1...ret-1] are lesser
  29.     // if not then set "ans_no"
  30.     for(int i=s+1; i<=ret-1; i++){
  31.         if(arr[i]>ele){
  32.             ans_no=1;
  33.             return ret;
  34.         }
  35.     }
  36.  
  37.     // checking all element in range [ret...e] are greater
  38.     // if not then set "ans_no"
  39.     for(int i=ret; i<=e; i++){
  40.         if(arr[i]<ele){
  41.             ans_no=1;
  42.             return ret;
  43.         }
  44.     }
  45.  
  46.     return ret;
  47. }
  48.  
  49. void postorder(int l, int r)
  50. {
  51.     // if indices are beyond boundary
  52.     if(l<0 || r>=n || l>r) return;
  53.  
  54.     // storing leftmost element (i.e. at index = l ) in ans[] array
  55.     ans[k++] = arr[l];
  56.  
  57.     // if l==r then no need to recurse
  58.     if(l==r){
  59.         return;
  60.     }
  61.  
  62.     // finding index of an element in array-range [l+1...r] which is greater than arr[l]
  63.     int ind = indexof(l+1, r, arr[l]);
  64.  
  65.     // if ans dose not exist then return
  66.     if(ans_no) return;
  67.  
  68.     // if "ind" is set then
  69.     //      recurse of right part first i.e. postorder(ind, r);
  70.     //      then for left part i.e.  postorder(l+1, ind-1);
  71.     // else if ind==-1
  72.     //      then recurse for remaining whole part i.e. postorder(l+1, r);
  73.     //      this would occur if a node in BST does not have left of right child.
  74.     if(ind!=-1){
  75.         postorder(ind, r);
  76.         postorder(l+1, ind-1);
  77.     }
  78.     else{
  79.         postorder(l+1, r);
  80.     }
  81. }
  82.  
  83. void solve()
  84. {
  85.     // resetting global variables
  86.     ans_no=0;
  87.     k=0;
  88.  
  89.     // scanning input
  90.     cin>>n;
  91.     for(int i=0;i<n;i++){
  92.         cin>>arr[i];
  93.     }
  94.  
  95.     // call to postorder
  96.     postorder(0, n-1);
  97.  
  98.     // if ans doesn't exist, print NO, and return
  99.     if(ans_no){
  100.         cout<<"NO"<<endl;
  101.         return;
  102.     }
  103.  
  104.     // print ans
  105.     for(int i=k-1;i>=0;i--){
  106.         cout<<ans[i]<<" ";
  107.     }
  108.  
  109.     cout<<endl;
  110. }
  111.  
  112. int main()
  113. {
  114.     ios_base::sync_with_stdio(0);
  115.  
  116.     int t=1; cin>>t;
  117.     while(t--){
  118.         solve();
  119.     }
  120.  
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0s 15304KB
comments (?)
stdin 
3
5
40 30 35 80 100
8
40 30 32 35 80 90 100 120
8
7  9 6 1 4 2 3 40
stdout 
35 30 100 80 40 
35 32 30 120 100 90 80 40 
NO
https://ideone.com/3Dz6Yz
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!