与えられたポストオーダートラバーサルからのBSTの構築

Question

私はBSTツリーサイズnのポストオーダー配列を持っています。それを構成することができる唯一のBSTがあることをどのように示しますか？右から左にノードを追加するとツリーを再構築できますが、右ツリーが1つしかないことをどのように表示しますか？

私は2本の可能な木があると言ってみました、それは可能ではないですが、それはBSTであるという理由だけで可能です

Answer 1

を行き詰まっ示す試してみました。有効なバイナリ検索ツリーのようにバイナリツリーのためにそれを思い出してください：

-leftサブツリー値
-leftと右のサブツリーのルートの値よりも大きくなければなりません値が
右回転のサブツリーのルートの値よりも小さくなければなりませんがなければなりません有効な2分探索木である。

これが当てはまる必要があることがわかっているので、ポストオーダーの要素のリストを与えられたツリーを再構成できます。配列の最後の要素（位置n）がルートです。ルートよりも右端の要素を見つけます。ルートの最初の右サブツリーです。ルートよりも小さい配列の最後に最も近い要素を見つけます。これが左の要素です。これを再帰的に適用してツリーを取得します。

例：それは左の部分木

11 
/
/ 

12右端のあるですので

[8,10,9,12,11] 

     11 <----root 

9は、11より小さく、最も右側の数であります11より大きい要素なので、

11 
/\ 
/ \ 
9  12 

は今、私たちの根は9で、9より小さい一番右の数は8であるので、木が

 11 
    /\ 
    / \ 
    9  12 
/\ 
    8 

なり、9よりも大きな次の番号が10で、最終的なツリーが

 11 
    /\ 
    / \ 
    9  12 
/\ 
    8 10 

です

これらの点で有効な別の有効なバイナリ検索ツリーがあることを確信してください。ではなく、は、ポストオーダートラバーサルで同じ出力を生成します。