問題タブ [lowest-common-ancestor]

コマンドラインでの入力は次のようになります。

ご覧のとおり、Node クラスを使用してハードコードすることもできますが、上記のようにコマンド ライン入力を使用してツリーを構築したいと考えています。

入力形式: 最初の数字は、家族内の一意の人数です。そして、家族の中で選ばれた2人。D、F、および残りの行には、スペースで区切られた 2 人の名前が含まれています。AB は、A が B の上位にあり、B が E および D の上位にあることを意味します。簡単にするために、AB である最初のセット、A をツリーのルートと見なす必要があります。

root = Node('A')では、コマンド ラインから入力を読み取り、 、 などで実行できるのと同じツリーを構築するにはどうすればよいroot.left = Node('B')でしょうか?

私はLCAを学ぼうとしているので、最も簡単な方法で正しい方向に助けていただければ幸いです.

ここに示されている問題があります。誰かがこの問題のアプローチを提案できますか? 社説を調べたところ、範囲ごとにツリーを作成し、それをノードとして扱うことになっているとありました.この概念とツリー変換のプロセスを理解できません.助けてくれてありがとう! 質問の詳細：

次の形式のシーケンスは、正しい括弧シーケンスと呼ばれます。

• 空のシーケンスは、正しい括弧シーケンスと見なされます。

• (A) は、正しい括弧シーケンスと見なされます。

• X と Y の両方が正しい括弧シーケンスである場合、XY は正しい括弧シーケンスと見なされます。

シーケンスが強い括弧シーケンスと呼ばれるのは、それが形式 (A) である場合に限られます。ここで、A は正しい括弧シーケンスです。

奇妙な合計を計算する必要があります: A の 2 つの部分配列ごとに [i1, j1] と [i2, j2] を取ります。部分配列は交差してはならず (つまり、i1 ≤ i2 および j1 ≤ i2)、強い括弧シーケンスでなければなりません。次に、サブ配列の最小長を合計に追加します。これは、強い括弧シーケンスでもあり、[i1, j1] と [i2, j2] の両方を含む (つまり、最小長のサブシーケンスが [i3, j3] の場合、[i3, j3] は強い括弧シーケンスであり、i3 ≤ i1 ≤ j1 ≤ j3 および i3 ≤ i2 ≤ j2 ≤ j3) です。

PS私は範囲のツリー変換の概念と、このコンテキストでLCAがどのように役立つかを理解できません.ありがとう.

ノード "a" とノード "o" からすべての LCA ノードを取得したいと考えています。

この DiGraph では、ノード "l" とノード "m" が LCA ノードです。

以下はコードです。

実行速度を速くしたい。

前述の方法以外で問題を解決するためのより良い方法があれば教えてください。

あなたの助けに感謝します。

私は次の実装に遭遇し、しばらく時間を費やしましたが、それでもアイデアを理解できません。誰かが行ごとにそれが何をしているのか説明してもらえますか? ノードが祖先であると判断できる時点がわかりません。

ありがとうございました

これは、バイナリ ツリー内の 2 つのノードの最も低い共通の祖先を非再帰的に見つけるために思いついたアルゴリズムです。基本的な戦略は次のとおりです。

1. 辞書/ハッシュテーブルを使用してツリーを保存します。各キーと値のペアは、ノードとその親を表します。
2. 2 つのノードのそれぞれから始めて、各ノードの値を表す変数をその親の値に設定し、通過した値をハッシュセット (2 つのノードごとに 1 つ) に格納することによって、ツリーを上っていきます。
3. 次の条件のいずれかが満たされると、検索は完了します。(a) 2 つのノードの値が等しい。または (b) 2 つのパスが互いに交差するとき (つまり、ノード 1 のトラバースされた値のハッシュセットにノード 2 の現在の値が含まれる、またはその逆)。または (c) 渡されたノードがツリーに存在しません (この場合、アルゴリズムは終了し、-1 を返します)。

私の理解では、アルゴリズムの最悪の場合の時間と空間の複雑さは O(log(n)) です。これは、ハッシュセットに 2 * 以上の高さのトラバーサルを行ったり、2 * 以上の高さの値を格納したりする必要がないためです (そして、ハッシュセットとツリー辞書のルックアップ時間は O(1)) です。

以下は私のコード（C＃）です。私の分析が正しいかどうか、またはこれを行うためのより効率的な（非再帰的な）方法があるかどうかを教えてください：

私の質問に対する答えは明白かもしれません。私はその明白な答えを紙の上で知っています。つまり、いくつかの例に関して言えば、Lowest Common Ancestor アルゴリズムを実行するためのループが許可されていない理由は理解できますが、DAG での LCA のソリューションについて書かれた論文を理解するのに問題があります。そして、ソリューションのどの部分が巡回グラフでの使用を妨げている..

私が知りたいこと、およびお知らせいただけるとありがたいこと:

• DAG の LCA 問題に対する解決策の 1 つを説明できますか?
• どのステップにサイクルの問題があり、その理由を特定できますか?

私の問題では、LCAを見つけるためのノードのペアが1つのループ内にないため、それを解決する方法があると思います..

前もって感謝します

再帰を使用せずに二分木の最低共通祖先を見つける方法は?