1

nary ツリーの LCA を見つけるために余分なスペースを使用せずに方法はありますか? 両方のノードの予約注文を保存し、共通のプレフィックスを見つける文字列を使用してそれを行いました

4

3 に答える 3

4

ノードがその深さを「認識」している場合、またはスペースにノードの深さを計算させたい場合は、下位ノードから上位ノードの同じ深さに戻ってから、一度に 1 レベル上に移動できます。会うまでの時間。

このコンテキストで「余分なスペース」が何を意味するかによって異なります。1 つの整数 (2 つのノードの深さの差) でそれを行うことができます。それはあまりにも多くのスペースですか？

別の可能性として、親ポインターがない場合、ポインター反転を使用できます。ポインターをトラバースするたびに、元の場所を記憶し、次にトラバースするポインターを記憶し、次のポインター トラバーサルの直前にします。 、そのポインターをバック ポインターに置き換えます。ツリーを復元するには、ツリーを上るときにこれを逆にする必要があります。これは、1 つのポインターのスペースを一時的に使用します。そして、上下に移動するときに深さを維持するための別の整数。探している 2 つのノードに対してこれを同期的に実行します。これにより、両方のトラバーサルで同じ高さになるまで下のノードから戻って作業し、共通のノードに到達するまで両方から作業を戻すことができます。 . これには、現在の深さごとに 1 つずつ、3 つの余分なメモリが必要です。1 つはポインターの反転中に使用される一時的なものです。非常に省スペース。その価値はありますか？

于 2012-04-04T13:19:57.167 に答える
3

戻って、二分木に対してそれを行います。二分木でできるなら、n分木でもできます。

二分木でのLCAへのリンクは次のとおりです。

n分木LCAに変換した後の様子は次のとおりです。

  public class LCA {

    public static <V> Node<V> 
                lowestCommonAncestor(Node<V> argRoot, Node<V> a, Node<V> b) {

      if (argRoot == null) {
        return null;
      }

      if (argRoot.equals(a) || argRoot.equals(b)) {
        // if at least one matched, no need to continue
        // this is the LCA for this root
        return argRoot;
      }

      Iterator<Node<V>> it = argRoot.childIterator();
      // nr of branches that a or b are on, 
      // could be max 2 (considering unique nodes)
      int i = 0; 
      Node<V> lastFoundLCA = null;
      while (it.hasNext()) {
        Node<V> node = lowestCommonAncestor(it.next(), a, b);
        if (node != null) {
          lastFoundLCA = node;
          i++ ;
        }
        if (i >= 2) {
          return argRoot;
        }
      }

      return lastFoundLCA;
    }

  }
于 2013-08-21T20:08:21.503 に答える
0

両方のノードに対して同期ウォークを実行します。

  • LCA=root で開始します。
  • ループ：
  • A がとるべきステップと B がとるべきステップを見つける
  • これらが等しい場合{LCA=ステップ。Aを決定します。Bを降ります。ループに移動します。}
  • done: LCA に A と B の lca が含まれるようになりました

C の疑似コード:

struct node {
        struct node *offspring[1234];
        int payload;
        };

        /* compare function returning the slot in which this should be found/placed */
int find_index (struct node *par, struct node *this);

struct node *lca(struct node *root, struct node *one, struct node *two)
{
struct node *lca;
int idx1,idx2;

for (lca=root; lca; lca=lca->offspring[idx1] ) {
    idx1 = find_index(lca, one);
    idx2 = find_index(lca, two);
    if (idx1 != idx2 || idx1 < 0) break;
    if (lca->offspring[idx1] == NULL) break;
    }
return lca;
}
于 2012-04-04T13:25:56.103 に答える