data-structures - 指定された 2 つのノードの共通の祖先を見つけるアルゴリズム

Question

2つのノードとツリーのルートがあれば。2 つのノードの共通の祖先を見つける方法は?

Answer 1

二分探索木を上から下にトラバース

しながら、n1 と n2 の間の値を持つ最初のノード n (つまり、n1 < n < n2) は、n1 と n2 の最下位または最小共通祖先 (LCA) です (ここで、n1 < n2)。したがって、BST を事前にトラバースします。n1 と n2 の間の値を持つノードが見つかった場合、n は LCA です。値が n1 と n2 の両方より大きい場合、LCA はノードの左側にあります。その値が n1 と n2 の両方よりも小さい場合、LCA は右側にあります。

面接でよく聞かれるプログラミングの質問で、面接サイトで簡単に解決策を見つけることができたはずです