問題タブ [least-common-ancestor]

就職面接で以下の質問をされました。

ルート ノード (適切に形成されたバイナリ ツリーへのノード) と他の 2 つのノード (ツリー内に存在することが保証されており、異なるものである) が与えられると、2 つのノードの最も低い共通の祖先を返します。

最小共通祖先アルゴリズムを知らなかったので、その場で作ってみました。次のコードを作成しました。

次のテスト ケースを試したところ、期待どおりの答えが得られました。

しかし、私のインタビュアーは、「あなたのアルゴリズムが None を返す木のクラスがある」と言いました。私はそれが何なのか理解できず、インタビューに失敗しました。アルゴリズムが 2 になることなくツリーの最下部に到達するケースは考えられません。ans何が欠けているのでしょうか?

Java で記述されたソートされたバイナリ ツリーで最小共通祖先を見つける非再帰アルゴリズム バージョンを検索しています。私が見つけたものはすべて、再帰バージョンのみです (stackoverflow や他の Web サイトでも)。

非再帰バージョン (while ループを使用) を書いたり、指示したりできますか? このバージョンが時間の複雑さの点でより効率的かどうかも書いてください?

そもそも、私は C や C++ を初めて使用するわけではありません。ただし、現在 Mac Yosemite で C++ を使用しています。キー (データ) 変数によって識別される 2 つのノードの共通の祖先を返す再帰関数を作成しようとしています。ロジックは単純で、両方のノードが同じブランチに入るまでツリーをトラバースします。これらのノードが分岐するノードが共通の祖先になります。これを念頭に置いて、次のコードを思いつきました。

私は働くべきです、私は同様のプログラムを行ってきました。ただし、プログラムはコンパイルされません。コンパイラエラーが発生"control may reach end of non-void function" します return ステートメントがあるため、これは奇妙です。また、このエラーを回避するために、ルート ノードのみを返す return ステートメントを最後に追加してみました。私は混乱しています... XCodeの設定で何かをする必要がありますか? 私の論理は間違っていますか？

現在、私はプログラムに取り組んでいます。そのステップの 1 つは、葉 c が二分木 T の他の 2 つの葉 a および b と同じサブツリーにあるかどうかをチェックすることです。私の現在のアプローチは次のとおりです。 T の葉の各ペアの LCA を取得し、辞書に格納します。次に、ツリーの各ノードについて、その子孫であるすべての葉を見つけて、辞書にも保存します。次に、c が a および b と同じサブツリーにあるかどうかを判断する必要がある場合、a および b の LCA を見つけ、c がその子孫であるかどうかを確認します。

このステップを多くの異なるペア a と b に対して実行する必要があり、600 ものリーフを持つバイナリ ツリーで実行する必要があります。この同じタスクを実行する、より高速なアルゴリズム、またはおそらくメモリ使用量が少ないアルゴリズムはありますか? ありがとう。

それを実現する関数を書くことを考える前に、アルゴリズムを考えようとします。h は、メインの親から特定のノードまでの最大距離として示されます。o(h^2) で実行する必要があります。つまり、そのようなアルゴリズムを考え出すのは簡単ですが、私は常に o(h) アルゴリズムを使用しています。実際に ah^2 操作を行っているかどうかを理解することになると、私も混乱します。私は本当にリードを使うことができました。

非二分木は通常どのように表されますか? ノードが持つことができる子の数に制限がないツリー。Adjacency Matrix または Adjacency List を使用して、サイクルがないと仮定するか、この質問に似たことを行うのが最善ですか ->

非二分木を実装する方法

n分木がある場合のフォローアップの質問（それはそれらの正しい名前ですか？）その木の2つの特定のノード/データ値の最小共通祖先を見つける良い方法は何ですか? 私が見つけることができるのは、このような二分木を扱うアルゴリズムだけです->

LCA アルゴリズムの O(nlog n) 前処理と O(log n) クエリを学習しようとしていました。Google翻訳の助けを借りてロシアのサイトから読んでいます。しかし、翻訳がうまくいかず、理解するのに苦労しています。 .誰でもこれで私を助けることができますか?

これは、そのWebサイトから取得した疑似コードです

私が理解したこと

• グラフをトラバースし、すべての頂点のインタイムとアウトタイムを保存していることはわかっています。

• 頂点up[i][j]の2^j祖先です。i

• 理由はわかりましたup[v][0]=p（2^0つまり、頂点の最初の祖先vはその父のみであるため）

• A上の関数が何をするのか理解できました.またはの前にどの頂点が発生したかを決定しBます.

• 私はアッパー(a,b)がLCAよりも真であることを理解してAおり、同様に2番目のステップです。

理解できないことは、疑似コードで私が言及しています。助けてください。すべてが正しいかどうかを理解したかどうかを確認してください。

PS->私の英語で申し訳ありません。これにはあまり慣れていません。

最も一般的でない祖先アルゴリズムについてはたくさんの質問がありますが、コンパイル時に LCA を決定しようとしており、単純化されたバージョンは次のように見えるかもしれませんが、ツリーはバイナリでも検索ツリーでもないため、これは異なります。 1。

parent別の同様の構造であるメンバー typedef を含む一連の構造があるとします。

一緒に次のような木を作ります

注: 構造体間に継承関係はありません。

私がやりたいのは、次のような型特性を作成するleast_common_ancestorことです。

これを行う最善の方法は何ですか？

特にツリーの深さが小さいため、アルゴリズムの複雑さには関心がありません。むしろ、正しい答えに到達する最も単純なメタプログラムを探しています。

編集：他のコンパイラの中でもmsvc2013でソリューションを構築できる必要があるため、ない回答constexprが優先されます。

グラフをコンポーネントに分割したい (下の例の DAG のように。コンポーネントを表すため、各ノードの色付きの識別子に注意してください)。画像内のコンポーネントを見つけた後、そのコンポーネントのルートと最後の子を見つけたいと思います。たとえば、青のコンポーネントを例にとると、ルートはEで、最後の子はHです。緑: ルートB- 最後の子H。

グラフの例:

コンポーネントに分割せずに- 、- 、E- 、-間の接続を見つけることができれば。それが私の最終目標なので、教えてください。HBEBHAI

コンポーネントのコンパイルについて。それが実は私の最終目標です。私が達成しようとしていることをよりよく理解してもらうために、それを含めたかっただけです。これらの接続を見つけたら、これはできません。

役に立ったが質問の答えにはならなかった質問:

• 有向非巡回グラフで最小共通祖先を見つけるアルゴリズム?

• ノードがゼロ、1 つ、または 2 つの親を持つ 2 つのリーフ ノードの最適な共通の祖先を見つける

（これらの回答で十分かもしれませんが、実装方法がわかりません）

ノート：

• すべてのサンプル コードを C++ または C# で投稿してください (サンプル コードを投稿する場合)

• これは私の最初の質問です。私が何か間違ったことをした場合は、私に知らせてください。

// 大きな編集: 質問を作り直して、私が望むものをより明確にしました。より役立つと思われるコンポーネントを導入しました。