アルゴリズム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 となる.

解法

一方のノードを P 他方を Q と呼ぶことにします. この問題を解くには, 親ノートから P, Q にいたる経路を何らかの情報で取得する必要があります.

たとえば全ノードを探索して, ノードをキーとに, その親を値に持つハッシュマップを構築することを考えます. そうすると, 平均ではO(1)で P -> Pの親 -> ... と Q -> Qの親 ->... と順にrootまで親をたどっていくことが可能になるので, お互いのrootまでの経路で最後に共通のノードだったものがLCAだということが分かります. 素直に両方の経路を比較すると O(MN) (M, Nはそれぞれの経路長) の時間がかかってしまうので, ここでも片方をまず走査して存在するノードをすべてハッシュマップ (あるいはSet, 集合でも構いません. 検索が平均で O(1) なデータ構造であることがキモです) に保存して, あらためて他方を順に走査していき, ハッシュマップに存在している最後の値を求めます.

Python code:

Java code:

計算量: O(K) (Kは与えられた木の要素数), これは子 -> 親 データを格納するハッシュマップの構築がボトルネックとなるためです.
空間量: O(K), これも上に同様です.

上ではハッシュマップを用いて子から親へとたどっていきましたが, もっと素直にrootからP, およびQへの親から子までの経路を保存する方法も有効です. この場合は root - P の経路, root - Q の経路をrootからたどっていき, 最初に２経路間で異なるノードが出現したときの直前のノードがLCAとなります.

Python code:

Java code:

経路はListでも問題無いですが, 先頭と末尾だけを扱うため Deque でも問題なく機能します. 再帰が少しわかりにくいですが, 対象のノードが見つからなかった場合は 経路に保存したノードは廃棄して状態を元に戻す必要があるため, findPath / constructPath メソッドの最後にその処理を行っています.