Lowest Common Ancestor of a Binary Tree
ヒープ順で配列 root に格納された二分木が与えられます。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあり、空の位置は -1 で表されます。値はそれぞれ異なり、特定の順序には従いません。
異なる2つのノードの値 p と q の最小共通祖先の値を返してください。これは、両方のノードを部分木に含む最も深いノードです。部分木にはその根のノードも含まれるため、q が p の下にある場合、答えは p です。
関数
- rootinteger-array
- 二分木をレベル順に並べ、空の位置には -1 を指定します
- pinteger
- 1つのノードの値
- qinteger
- 別のノードの値
- 戻り値integer
- 部分木に p と q の両方を含む、最も低いノードの値
制約
2 ≤ root.length ≤ 32767- 各
root[i]は-1、または0 ≤ root[i] ≤ 104を満たす値です。 root[0]が-1になることは決してなく、木には少なくとも 2 つのノードがあります。- 配列の末尾には、最後のノード以降に余分な
-1の要素が含まれる場合があります。 - 空の場所の子は両方とも空であり、深さは最大でも
14です。 - 木内のすべての値は互いに異なり、特定の順序には従いません。
pとqは、ツリー内の異なる2つのノードの値であり、順序は問いません。
例
- 入力
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- 出力
- 3
- 説明
6は3の左の子で、9は3の右側にある4の下にあるため、3で合流します。値を比較すると、根の8が指し示されます。6はそれより小さく、9はそれより大きいです。
- 入力
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- 出力
- 4
- 説明
7は4の左の子であり、4の部分木には4自身が含まれるため、答えは4です。
- 入力
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- 出力
- 6
- 説明
- 根の
1には左の子がありません。その右の子6は左に3、右に0を持つため、値は6で合流します。
発展問題
答えを-1とする場合、pまたはqが存在しない可能性があると、1回の走査でどのショートカットが使えなくなりますか？また、どうすればそれでも1回の走査で完了できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
最初の例で探索木のルールを試してみましょう。
6は根の8より小さく、9は大きい値です。それらは実際にはどこにありますか？この木で値を比較することについて、何がわかりますか？各部分木は、見つけたものを親に伝えます。何も見つからなかったか、2つの値のどちらか、あるいは答えです。両方の子から値について聞いたノードで、
pとqが出会います。空の位置では
-1を返し、root[i]がpまたはqの場合はiを返し、両方の子がインデックスを返す場合もiを返し、それ以外の場合は-1ではない子の結果を返す、再帰的なfind(i)を書きます。答えはroot[find(0)]です。
解説
どちら側が値を保持しているかは順序からは分からないため、自分で確認する必要があります。後順走査を1回行えば、各部分木が見つけたものを報告でき、両側から情報を受け取った最初のノードで値が出合います。
下へ進みながら、各側を探します
考え方
根から下へ進み、各ノードで左部分木を探索して p と q を探します。両方ある場合は左へ進みます。どちらもない場合は右へ進みます。それぞれ一方ずつある場合は値が分かれるので、このノードが答えです。p または q を持つノードも答えになります。もう一方の値は必ずその下にあるからです。6 と 9 の場合、根では両方とも左側に見つかり、3 では、単独の 6 だけが p を持っています。
下へ進むたびに部分木全体を探索するため、h レベルでは O(n·h) のコストがかかり、深さの上限がない細長い木では O(n²) になります。8 での探索では、すでに 3 の下にあるすべてのノードを訪れており、3 でのステップで一部を再び訪れます。
アルゴリズム
contains(i, value)を実装します。空の場所（末尾の先、または-1）ならfalse、root[i]がvalueと等しければtrueを返し、それ以外の場合は両方の子を調べます。i = 0から始めます。root[i]がpまたはqなら、それを返します。2*i+1にある左部分木が両方の値を含む場合は、そこへ進みます。どちらの値も含まない場合は、2*i+2へ進みます。- それ以外の場合は
root[i]を返します。
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each side1回の後行順走査
考え方
各部分木は、下から上へ一度だけ答えを返します。find(i)は、iの部分木が両方の値を持つ場合は答えのインデックスを、どちらか一方を持つ場合はpまたはqのインデックスを、どちらも持たない場合は-1を返します。
pまたはqを持つノードは、下を調べずに自身のインデックスを返します。もう一方の値がその部分木にあれば、このノードが答えです。なければ、より上のノードが両側から結果を受け取ります。それ以外のノードは、両方の子に問い合わせます。結果が2つあれば、値が別々の側から上がってきて、ここで合流したことを意味します。結果が1つだけなら、それが一方の値でも完成した答えでも、そのまま上へ渡します。
最初の例では、3は左からインデックス3を、右から10を受け取り、自身のインデックス1を返し、ルートがそれを上へ渡します。各ノードは一度だけ訪問されます。時間計算量はO(n)、再帰の空間計算量はO(h)です。
アルゴリズム
- インデックスが末尾を過ぎている場合、または
-1の場合、find(i)は-1を返します。 - 値が
pまたはqのノードは、下を調べずにiを返します。 - それ以外のノードは
left = find(2*i+1)とright = find(2*i+2)を計算します。どちらも-1でなければiを返し、そうでなければ-1ではない方、または-1を返します。 root[find(0)]を返します。
def lowestCommonAncestor(root, p, q):
n = len(root)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or root[i] == -1:
return -1
if root[i] == p or root[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return root[find(0)]
落とし穴と境界ケース
- 値をノードと比較している。木には順序がないため、最初の例では探索が
3ではなくルートの8で止まる。 - インデックスではなく
trueまたはfalseを返している。親ノードは、見つかった答えがすでにその下にあるかどうかを判断できない。 - 長さを確認せずに子ノードを読み取っている。インデックス
10にある9の子のインデックスは21と22で、最後の要素を超えている。 - インデックスである
find(0)ではなく、root[find(0)]を返す。 - LuaとRでは配列は1から始まる。ノードのインデックスは0ベースのままにして、
root[i + 1]を読み取る。
よくある質問3
二分木の最小共通祖先の時間計算量はどのくらいですか？
後順走査では各ノードに入るのは最大1回なので、時間計算量は O(n) です。再帰スタックには各階層につき1つのフレームが保持されるため、平衡木では空間計算量は O(log n)、パス状の木では O(n) です。
これは二分探索木における最小共通祖先とどう違いますか？
探索木では、p と q をノードと比較すれば、それぞれがどちら側にあるかがわかるため、根からの1つの経路をたどれば O(h) で答えが見つかります。ここでは、比較しても何もわからないため、部分木を探索します。
親ポインタを使って最小共通祖先を見つけられますか？
はい。この配列では、インデックス i の親は (i-1)/2 を切り捨てた値です。2つのインデックスのうち大きい方を親へ移動し、両者が等しくなるまで繰り返します。大きいインデックスが小さいインデックスの祖先になることはありません。連結ノードの場合は、p の祖先を集合に入れ、q から親へたどって、集合内にある最初のノードを見つけます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def lowestCommonAncestor(root, p, q):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
期待される出力
3