与えられたツリーのポストオーダーデータの文字列を作る

Question

私の割り当ての一部として、私は表現ツリーが与えられており、O（n）ランタイムでイン・フィックスに変換する必要があります。 "（（1 V（2 H（3 V 4）））H（5 V 6））" には、このツリーを変換する 例えば、

。 私はそれをそのままインフィックスに変換する方法を考えることができなかったので、最初にそれをポストフィックスとイン・フィックスに変換することを考えました。 （もっと良い方法があれば教えてください）。

私の問題は、ツリーをポストオーダーに変換することです。 私は次のことを試してみました：

private String treeToPost(Node node, String post) { 
    if (node != null) { 
     treeToPost(node.left, post); 
     treeToPost(node.right, post); 
     post = post + node.data.getName(); 
    } 
    return post; 
} 

それだけで、それは旅の最後のノードを節約するために今、私は二つ目は、私はということで、最初のものは、それが動作しないで、この方法には二つの問題を、持っていますそのたびに新しい文字列を作成する必要があるため、O（n）で実行されるかどうかはわかりません。 ここでこの問題の解決策を見つけましたが、StringBuilderを使用しましたが、これは使用できません。データを保存するための文字列を作ることを考えましたが、ツリーのサイズがわからないので、必要な配列のサイズを知ることはできません。 ありがとうございました:)

Answer 1

おそらく中止に行くのはおそらくかっこを追加するだけです。

第二に、このような何かを行うと、すべてのノードを保存します：

private String treeToPost(Node node) { 
    String returnString = ""; 
    if (node != null) { 
     returnString += treeToPost(node.left); 
     returnString += treeToPost(node.right); 
     returnString += node.data.getName(); 
    } 
    return returnString; 
} 

中置の場合、これは

private String treeToPost(Node node) { 
    String returnString = ""; 
    if (node != null) { 
     returnString += "(" + treeToPost(node.left); 
     returnString += node.data.getName(); 
     returnString += treeToPost(node.right) + ")"; 
    } 
    return returnString; 
} 

動作するはずですこれらの両方の新しい文字列が毎回オブジェクトを作ります。だから私はそれが技術的にはO（n^2）だと思う。なぜなら文字列が毎回大きくなるからだ。しかし、私の教授はそれについてのポイントを差し引くことはない。 ただし、この動作を回避したい場合はStringBuilderを使用できません。 CharArrayWriterを使用できます。これは動的に増加するバッファです。次に、2つの方法を実行できます。バッファに追加され、何も返さないもの。そして、Stringを返すもの。次に、String1の中からバッファー1を呼び出します。