特定の配列がバイナリ検索ツリーのポストオーダートラバーサルを表しているかどうかをチェックする方法？

Question

ある配列があり、それがBSTのポストオーダートラバーサルを表すかどうかを知る必要があります。 （例：ポストオーダーの代わりに質問があった場合は、配列が時刻o（n）でソートされているかどうかだけチェックする必要があります）

Answer 1

クイックサニティチェック：配列の最後の項目がルートノードの場合、それはポストオーダートラバーサルの結果ではありません。同様に、配列内の最初の項目は、先行順走査が行われた場合のルートです。

Answer 2

{LEFT Subtree} {Right Subtree} {ROOT}によってポストオーダートラバーサルが行われます。したがってここでの考え方は、右端から配列を横断することです。配列の最後の要素はルートで、右から左へと、小さい要素に遭遇したときに左のサブツリーで始まる境界をマークすると、BSTはこのインデックスから大きな要素を持ちません。これは各サブツリーに適用されます。 C++でのアルゴリズムは、このように書きます -

bool isBST(int arr[], int n){ 

//Set root to the max integer value. 
int root = INT_MAX; 

//Stack used to keep track of current subtree 
std::stack<int>s; 

//Start at the end of the array because Postorder traversal is 
// <L><R><D> 
for (int i = n-1; i>=0; i--) { 
    //False if any larger number in the left subtree 
    if (arr[i]> root) { 
     return false; 
    } 

    //Reset the root for boundary of every subtree, 
    //when current item is smaller than top, 
    //that means we are starting with left subtree of this root 
    while (!s.empty() && arr[i] < s.top()) { 
     root = s.top(); 
     s.pop(); 
    } 
    //Keep pushing the elements otherwise 
    s.push(arr[i]); 
    } 
    return true; 

}