アルゴリズム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 となる. 解法 一方のノード
Lowest common ancestor - Wikipedia
In this tree, the lowest common ancestor of the nodes x and y is marked in dark green. Other common ancestors are shown in light green. In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Return the Boss in the hierarchy -- Tried to apply Depth First Search
