Lowest Common Ancestor of a BST
二分探索木が配列 tree にレベル順で格納されており、その中に p と q という2つの値がどちらも存在します。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾に余分な -1 が含まれる場合があります。二分探索木では、ノードの左部分木にあるすべての値はそのノードの値より小さく、右部分木にあるすべての値は大きくなります。
lowestCommonAncestor という名前の関数を作成し、p と q の最小共通祖先の値を返してください。最小共通祖先とは、両方を部分木に持つ最も深いノードです。ノードはそれ自身の部分木に含まれるため、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は8の左の子で、15は8の右側で12の下にあります。それぞれのノードから上へたどると、両方が最初にたどり着くノードは8なので、それが答えです。ルートの20も共通の祖先ですが、より上位にあります。
- 入力
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- 出力
- 12
- 説明
10は12の左の子です。ノードは自分自身の祖先として数えられるため、12の部分木には両方の値が含まれますが、その下のノードには含まれません。したがって、答えは12です。値の順序はどちらでもかまいません。ここではpのほうが大きい値です。
- 入力
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- 出力
- 70
- 説明
55と80はどちらもルートの50より大きいため、どちらもその右側にあります。70で分かれます。55は小さいので左側（60の下）にあり、80は大きいので右側にあります。したがって、答えは70です。
提出時に隠しテスト+12件
発展問題
ツリー内にpまたはqが存在しない可能性があり、その場合は関数が-1を返さなければならないとしたら、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートに立ちます。
pとqの両方がその値より小さい場合、両方のノードはどちらのサブツリーにありますか？両方の値が現在のノードの同じ側にある限り、さらに下にあるすべての共通祖先もその側にあります。両者が同じ側にない最初のノード、またはそのノードがどちらか一方を保持している場合のそのノードが、求めるノードです。
インデックス
0から開始します。両方の値がtree[i]より小さい間は、2*i+1に移動します。両方の値がより大きい間は、2*i+2に移動します。それ以外の場合はtree[i]を返します。
解説
通常の二分木では、各ノードの左右両方を探索しないと、値がどこにあるか分かりません。二分探索木では、各ノードで、より小さい値は左側、より大きい値は右側にあることが分かります。そこで、ルートから始めて、両方の値がある側へ進みます。2つの値が同じ側になくなる最初のノードが答えです。木の残りを調べることなく、1つの経路をたどれば見つけられます。
順序を無視して、木全体を検索する
考え方
まず、配列内をどのように移動するかです。インデックス i のノードは、左の子を 2*i+1 に、右の子を 2*i+2 に持ちます。子が実在するのは、そのインデックスが配列内にあり、そこにある値が -1 ではない場合だけです。[20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] では、ルートの 20 はインデックス 1 と 2 に 8 と 31 を持ち、インデックス 4 の 12 は、インデックス 9 と 10 に 10 と 15 を持ちます。
この最初の方法は、どのような二分木にも使えます。再帰関数 find(i) は、インデックス i にある部分木の内容を報告します。空の場所は -1 を返します。p または q を持つノードは自分自身を返します。もう一方の値がその下にあれば、それが答えであり、もう一方の値が別の場所にあれば、より上のノードが両方を見つけるからです。それ以外の場合、ノードは左右両方の子に尋ねます。両方の側が何かを返したなら、p は一方に、q はもう一方にあるため、このノードが両者の合流点です。一方の側だけが何かを返したなら、それを上に渡します。
p = 3、q = 15 の場合、8 は左からインデックス 3 を、右からインデックス 10 を受け取るので、自分自身を返します。ルートは左からそれを受け取り、右からは -1 を受け取るため、8 を上に渡します。
これは正しい方法ですが、すべてのノードを訪れる可能性があり、時間計算量は 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つの探索経路を比較する
考え方
では、この順序を使いましょう。二分探索木で値を検索する方法に従って値を見つけられます。ルートから始め、値がノードより小さければ左へ、大きければ右へ進み、その値にたどり着いたら止まります。この探索経路は、その値のすべての祖先を通り、それ以外は通りません。ルートからノードまでの経路は一意だからです。
p の探索経路と、q の探索経路を記録します。どちらもルートから始まり、値が別々の方向へ進むまで同じノードをたどります。共通する最初の部分が両者の共通祖先のリストなので、最後に共通する値が最も低い祖先です。3 と 15 の経路は 20, 8, 3 と 20, 8, 12, 15 です。共通するのは 20, 8 なので、答えは 8 です。12 と 10 の経路は 20, 8, 12 と 20, 8, 12, 10 で、答えは 12 です。
各探索経路は1レベルにつき1ステップ進むので、時間計算量は O(h) です。ここでは木にいくつノードがあっても、最大14ステップです。2つのリストに必要な空間計算量は 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 より小さく、もう一方が大きい場合は、2つは別々の部分木にあり、v の子ノードのどれも両方を含みません。または、一方の値が v と等しい場合で、ノードは自分自身の祖先です。いずれの場合も、v は両方の上にある最も深いノードです。
3つ目の例では、ルートの 50 は 55 と 80 の両方より小さいため、右へ進んで 70 に行きます。そこでは 55 は小さく、80 は大きいため、答えは 70 です。2つ目の例では、20 から 8、そして 12 へ進み、p と等しくなるので停止します。
ルートから1つの経路だけをたどり、各レベルで値のペアを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のとき、p ≤ 12かつq ≤ 12という判定では答えの先にある10まで進み、そこから探索が10を返すか、木の外に出てしまいます。両方の値が同じ側に厳密にある場合にのみ移動してください。 p < qと決めつけること。値の順序は任意です。両方の値をノードと比較するか、先に入れ替えてpを小さい方にしてください。- 一方の値がもう一方の祖先である場合を考慮し忘れること。その場合、答えはその値自体であり、その親ではありません。
- 値ではなくインデックスを返すこと。この関数が返すのは
iではなくtree[i]です。 - 木全体を探索すること。正しい答えは得られますが、1本の経路で十分なのに、最大ですべてのノードを訪問してしまいます。
- 配列のインデックスが1から始まるLuaとRで、オフセットを混同すること。
2*i+1の計算ではノードのインデックスを0ベースのままにし、tree[i + 1]を読み取ってください。
よくある質問4
BSTにおける最小共通祖先の時間計算量はどれくらいですか？
根からの走査は1つの経路をたどるため、深さが h の木では時間計算量は O(h)、追加の空間計算量は O(1) です。平衡木では O(log n)、単一路の形をした木では O(n) です。
二分探索木におけるLCAは、二分木におけるLCAとどのように異なりますか？
通常の二分木では、値はどこにでもある可能性があるため、各ノードの両方の部分木を検索し、計算量は O(n) です。二分探索木では、2つの値をノードと比較することで、それぞれがどちら側にあるかがわかるため、根から1本の経路をたどります。再帰的な任意の木の方法も二分探索木で使えますが、その情報を活用できません。
ノードが自身の最小共通祖先になることはありますか？
はい。ノードはそれ自身の祖先として数えられるため、p が q より上にある場合、答えは p です。2つの値が等しい場合も、同じルールにより p になります。この探索はどちらの場合にも対応しており、現在のノードがいずれかの値と一致するとすぐに停止します。
なぜ、p と q が分かれる最初のノードで探索を止めるのでしょうか？
そのノードでは一方の値が小さく、もう一方の値が大きいため、それぞれ異なる部分木にあります。その下にあるノードはどちらか一方の部分木にしか属さず、両方を持つことはできません。分岐するノードは両方を持ち、それより深いノードはどちらも持たないため、これが最低共通祖先の定義そのものです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
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