問題タブ [postorder]

ポストオーダー方式で列挙された完全な二分木があります。そのようなツリーの例は次のとおりです。

木の大きさはよくわかります。入力として単一の数値（関心のある頂点のID）を取り、単一の数値（親のID）も返す数式または単純なアルゴリズムを探しています。ツリーを上からトラバースして結果を取得するのは非常に簡単O(log n)です。より速い解決策はありますか？私は主に葉に興味があるので、特別な場合の解決策があれば、それも持ってきてください.

EulerTour を二分木で表示するコードを書きたかったのです。私は以下のコードを書きました：

しかし、私には3つの質問があります:

1. オイラーツアーでいいの？？

2. もしそうなら、tree の postOrder Traverse と非常によく似ているようです。右？

3. ポスト オーダー トラバースに似ている場合、2 つの分離コードを使用する違いは何ですか?

前もって感謝します

このアルゴリズムに従ってBST(binary search tree)、指定されたから構築するコードを実装しています。後戻りはしません。私は意味のないものを得ています。ここに私のコードがありますpost-order traversal arraybinary Search Tree

印刷したときの出力pre-order traversal is 5 9 6 8 3 4が正しくありません。

私が間違っている可能性がある場所はありますか？

編集:行の順序を交換した後root.right and root.left(以前はコメントアウトされていました)、left tree正しく構築されていますが、正しいツリーはそうではありません。私が得る出力は 5 3 1 4 9 6 8

私は BST に取り組んでおり、現在ツリー トラバーサルを試みています。私のインオーダー トラバーサル出力は事前オーダーによって正しくなり、ポストオーダー出力は正しくなりません。私のコードは

予約注文で私が得ている出力は

4-1-2-3-5-6-7

そうではないはずなのに

4-1-2-3-6-5-7

. 同様に、注文後の出力は

1-2-3-5-6-7-4

あるべきなのに

3-2-1-5-7-6-4

.

どこが間違っているのかわかりません。

一意の要素を持つ非バイナリ ツリーの事前順および事後順トラバーサルを考えると、元のツリーをどのように作成するのでしょうか?

例えば

preorder = ABCDEF
および postorder = BCEFDA の場合

~~A~~~~~
~/~|~\~~~
B~C~D~~
~~~~/~\~~
~~~E~~F~に相当するツリーを構築する必要があります

（チルダについては申し訳ありませんが、ツリーを正しく表示し、読みやすくする方法を理解できる唯一の方法でした）

とにかく、これは宿題のプロジェクトであり、コード自体は問題ではないので、コードにこれを行うよう求めているわけではありません。私が助けを必要としているのは、適切なツリーを確実に作成するように2つの入力を比較するアルゴリズムです

PS指定されたツリーは、任意の数（おそらく<= 26）のノードで多かれ少なかれ複雑になる可能性があります

TL;DR
How do I use Pre-order and Post-order traversals to construct their original tree