Lowest Common Ancestor of a BST
ヒープ順序で配列 tree に格納された二分探索木が与えられます。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあり、-1 は空の位置を示します。ノードの左部分木にあるすべての値はそのノードの値より小さく、右部分木にあるすべての値はそのノードの値より大きくなります。
値 p と q（どちらも木に存在します）の最も低い共通祖先の値を返す lowestCommonAncestor を書いてください。最も低い共通祖先とは、その部分木に両方の値を含む最も深いノードです。ノードは自身の部分木に含まれるため、p が q より上にある場合、答えは p です。
関数
- treeinteger-array
- 二分探索木をレベル順で表し、空の位置には -1 を指定
- pinteger
- 最初に見つける値
- qinteger
- 2番目の値を見つける
- 戻り値integer
- 部分木に p と q の両方を含む最も深いノードの値
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1または0 ≤ tree[i] ≤ 105を満たす値です。 tree[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列は最後のノードの後に、余分な
-1の要素が続く場合があります。 - 空の場所の両方の子も空であり、深さは最大でも
14です。 - この木は有効な二分探索木なので、すべての値は異なります。
pとqは、木の中のノードの値です。順序は任意で、同じ値の場合もあります。
例
- 入力
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- 出力
- 8
- 説明
3と15からたどっていくと、両方が最初に到達するノードは8です。3はその左の子で、15は右側の12の下にあります。ルートの20も共通の祖先ですが、より上にあります。
- 入力
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- 出力
- 12
- 説明
10は12の左の子であり、ノードは自身の祖先としても数えられるため、12は両方の値を持ち、それより下のノードはどちらの値も持ちません。ここではpのほうが大きい値です。
- 入力
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- 出力
- 70
- 説明
- 両方の値はルート
50より大きいため、どちらも右側にあります。70で分かれます。55は小さいので左側の60の下にあり、80は大きい値です。
発展問題
p または q がツリーに存在しない可能性があり、その場合に関数が -1 を返さなければならないとしたら、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートに立ちます。
pとqの両方がその値より小さい場合、両方のノードはどちらのサブツリーにありますか？両方の値が現在のノードの同じ側にある限り、さらに下にあるすべての共通祖先もその側にあります。両者が同じ側にない最初のノード、またはそのノードがどちらか一方を保持している場合のノードが、求めるノードです。
インデックス
0から開始します。両方の値がtree[i]より小さい間は2*i+1に移動し、両方の値が大きい間は2*i+2に移動します。それ以外の場合はtree[i]を返します。
解説
探索木では、各ノードで値がどこにあるかがわかります。小さい値は左、大きい値は右です。ルートから始めて、両方の値がある側へ進みます。値が同じ側を共有しなくなる最初のノードが答えで、そこへは1つの経路でたどり着けます。
順序を無視して木全体を探索する
考え方
この方法は、あらゆる二分木で動作します。再帰的な find(i) は、i の部分木が何を含んでいるかを報告します。p または q を含むノードは、自分自身を報告します。もう一方の値がその下にあればそれが答えとなり、そうでなければ、より上位のノードが両方を見つけます。それ以外のノードは、両方の子に問い合わせます。両方が何かを報告した場合、p と q は異なる側にあり、このノードが両者の合流点です。片方だけが報告した場合は、それを上に渡します。
3 と 15 の場合、8 は左からインデックス 3 を、右からインデックス 10 を受け取り、自分自身を報告します。すべてのノードを訪問する可能性があります。時間計算量は O(n)、再帰の空間計算量は O(h) です。
アルゴリズム
find(i)を書きます。iの位置が空（末尾より後、または-1）なら、-1を返します。tree[i]がpまたはqなら、iを返します。2*i+1と2*i+2に対してfindを呼び出します。両方で何かが見つかった場合は、iを返します。- それ以外の場合は、見つかった側の値を返すか、どちらも見つからなければ
-1を返します。 tree[find(0)]を返します。
def lowestCommonAncestor(tree, p, q):
n = len(tree)
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 tree[i] == -1:
return -1
if tree[i] == p or tree[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 tree[find(0)]2つの探索経路を比較する
考え方
通常の方法で値を検索します。ルートから始め、値がノードより小さければ左へ、大きければ右へ進みます。ルートからノードまでの経路は一意なので、この探索ではその値の祖先すべてを通り、それ以外は通りません。
2つの探索経路を記録します。値の進む方向が分かれるまでは同じノードを通るため、共通する最初の部分に共通の祖先が並び、その最後の値が最も低い祖先です。3と15の場合、経路は20, 8, 3と20, 8, 12, 15です。共通するのは20, 8なので、答えは8です。それぞれの探索は各レベルで1ステップ進むため、時間計算量はO(h)、リストに必要な空間計算量はO(h)です。
アルゴリズム
path(target)を記述します。インデックス0から開始し、tree[i]を記録します。それがtargetと等しければ停止し、そうでなければtargetが小さい場合は2*i+1へ、大きい場合は2*i+2へ移動します。pへのパスとqへのパスを作成します。- 両方のリストを先頭からたどり、共有する最後の値を返します。
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answer値が分かれるまで下に進みます
考え方
p と q が同じ方向に進む間、2つの経路は一致するため、両方を同時にたどります。v を持つノードで、両方の値が小さければ、どちらも左部分木にあり、v より下にある共通祖先もすべて左側にあります。左へ進みます。両方の値が大きければ、右へ進みます。
それ以外の場合、一方の値は小さく、もう一方は大きいため、v の子のどちらも両方の値を持ちません。または、どちらかの値が v と等しく、その値自身が祖先です。いずれの場合も、v は両方の値の上にある最も深いノードです。3つ目の例では、50 は両方の値より小さいため、右へ進んで 70 に到達します。そこで 55 は小さく、80 は大きくなっています。各レベルで比較を1組行うため、時間計算量は O(h)、空間計算量は O(1) です。
アルゴリズム
- インデックス
i = 0から開始します。 v = tree[i]を読み取ります。p < vかつq < vの場合、2*i+1に移動して繰り返します。p > vかつq > vの場合、2*i+2に移動して繰り返します。- それ以外の場合は
vを返します。
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
落とし穴と境界ケース
- 移動判定に
≤と≥を使う。p = 12、q = 10の場合、探索は12を通り過ぎて10まで進み、その後10を返すか、木の範囲外に進んでしまう。 p < qと仮定する。2つ目の例ではpのほうが大きい値だ。両方をノードと比較するか、先に入れ替える。- 値ではなくインデックスを返す。答えは
iではなくtree[i]だ。 - Lua と R では、配列のインデックスは1から始まる。
2*i+1の計算ではノードのインデックスを0始まりのままにして、tree[i + 1]を読み取る。
よくある質問3
BST における最低共通祖先の時間計算量はどれくらいですか？
ルートからの探索は1つの経路をたどるため、深さがhの木ではO(h)時間かかり、追加の空間はO(1)です。平衡木ではO(log n)、単一の経路のような形をした木ではO(n)です。
二分探索木のLCAは、二分木のLCAとどのように異なりますか？
通常の二分木では、値はどこにでも存在し得るため、すべてのノードを検索することになり、作業量は O(n) です。二分探索木では、2つの値とノードを比較すれば、それぞれがどちら側にあるかが分かるため、ルートから1つの経路をたどります。
ノードはそれ自身の最小共通祖先になれますか？
はい。ノードは自身の祖先として数えられるため、pがqより上にある場合、答えはpです。また、2つの値が等しい場合、答えはその値です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def lowestCommonAncestor(tree, p, q):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
期待される出力
8