アルゴリズム1000本ノック（１０）: Lowest Common Ancestor of a Binary Tree - たぶん動くと思う...
問題 LeetCode より拝借しています. ２分木とそのノードである２点が与えられた時, ２点の最も下位の 共通親ノード = lowest common ancestor (LCA) を返却するアルゴリズムを実装せよ. WikipediaによるLCAの定義: "The lowest common ancestor とは２分木 T における２ノード v, w 間において v, w両方を子孫に持つ中で最も下層にある親ノードを指す. (v, wの一方が他方の親となっている場合も含める)." _______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 例えば, 上の木においてノード 5 と 1 の the lowest common ancestor (LCA) は 3 となる. また 5 と 4 の場合は 5 となる. 解法 一方のノード
有向非巡回グラフ - Wikipedia
有向非巡回グラフの例。この例は連結グラフであるが、非連結な有向非巡回グラフも存在する。 有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点から出発し、辺をたどり、頂点に戻ってこないのが有向非巡回グラフである[1][2][3]。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回
グラフ理論 - Wikipedia
グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。 グラフ（データ構造）などの応用がある。 グラフによって、様々なものの関連を表すことができる。 6つの節点と7つの辺から成るグラフの一例 例えば、鉄道や路線バス等の路線図を考える際には、駅（節点）がどのように路線（辺）で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。 したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。 このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり[1]、グラフがも
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Return the Boss in the hierarchy -- Tried to apply Depth First Search
