Validate Binary Search Tree
レベル順に配列 tree に格納された二分木が与えられます。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾には余分な -1 の要素が含まれる場合があります。
二分探索木であれば true を、そうでなければ false を返す、isValidBST という名前の関数を書いてください。二分探索木では、すべてのノードの値は左部分木のすべての値より厳密に大きく、右部分木のすべての値より厳密に小さくなければなりません。有効な木に、同じ値が2つ含まれることはありません。
関数
- treeinteger-array
- 空の位置を -1 で表し、二分木をレベル順に
- 戻り値boolean
- 木が二分探索木であれば true、そうでなければ false
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1、または0 ≤ tree[i] ≤ 105を満たす値です。 tree[0]が-1になることはないため、木には少なくとも1つのノードがあります。- 配列は、最後のノード以降に余分な
-1の要素が続く場合があります。 - 空の位置の子も両方とも空であり、深さは最大でも
14です。 - 値は繰り返される場合があります。
例
- 入力
- tree = [8, 3, 12, 1, 6, 10, 15]
- 出力
- true
- 説明
- 各ノードは、その上にあるすべてのノードに対して正しい側にあります。順に（左部分木、ノード、右部分木）読み取ると、値は
1, 3, 6, 8, 10, 12, 15となり、厳密に増加しています。これが探索木の性質です。
- 入力
- tree = [10, 5, 15, -1, -1, 6, 20]
- 出力
- false
- 説明
- すべてのノードは左の子より大きく、右の子より小さいですが、それでもこの木は有効ではありません。インデックス
5にある6はルート10の右部分木にあるため、10より大きくなければなりませんが、そうではありません。
- 入力
- tree = [12, 7, 12]
- 出力
- false
- 説明
- ルートの右の子は
12を持っており、ルートと同じ値です。右部分木の値は厳密に大きくなければならないため、同じ値だとルールに違反します。
提出時に隠しテスト+16件
発展問題
インデックス i のノードの親は、切り捨てた (i-1)/2 の位置にあります。スタックを保持したり再帰したりする代わりに、親ノードをたどりながら、追加のスペース O(1) で木を順番に走査できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
[10, 5, 15, -1, -1, 6, 20]では、すべてのノードが左の子より大きく、右の子より小さくなっています。それでも、なぜ二分探索木ではないのでしょうか？すべての祖先ノードは、そのノードに制限を設けます。ノードが祖先の左側にある場合はその値より小さく、右側にある場合はその値より大きくなります。これらの制限を合わせると、1つの開区間になります。値
vから左に進むと上限がvに下がり、右に進むと下限がvに上がります。(index, low, high)のスタックを保持します。ルートから始め、許容されるすべての値より広い範囲を設定します。エントリを取り出し、値が範囲内に厳密に収まっていなければ失敗とし、それぞれの実際の子を範囲を狭めてスタックに追加します。
解説
このルールは、ノードとその2つの子ではなく、部分木全体に関するものです。すべてのノードで親子の条件を満たしていても、木が正しいとは限りません。深い位置にあるノードが、何階層も上の祖先によって設定された範囲を破ることがあるからです。これをすっきり扱う方法は2つあります。木を順序どおりに読み、値が厳密に増加していることを確認する方法と、各ノードに祖先が許容する値の範囲を渡し、その範囲内にあることを確認する方法です。
各ノードをその左右の部分木全体と比較する
考え方
まず、配列内をどのように移動するかを見てみましょう。インデックス i のノードの左の子は 2*i+1 に、右の子は 2*i+2 にあります。子ノードが実在するのは、そのインデックスが配列内にあり、そこにある値が -1 ではない場合だけです。[10, 5, 15, -1, -1, 6, 20] では、ルート 10 の子である 5 と 15 はそれぞれインデックス 1 と 2 にあり、15 の子である 6 と 20 はそれぞれインデックス 5 と 6 にあります。
多くの人が最初に試す方法は、各ノードとその2つの子だけを比較することです。この木を見ると、それではうまくいかない理由がわかります。5 < 10、15 > 10、6 < 15、20 > 15 はすべて成り立ちますが、6 は 10 の右側にあります。定義では部分木に含まれるすべての値について述べているので、まさにそこを確認しましょう。
値 v を持つノードについて、その左側にあるすべての値が v より小さいのは、左側の最大値が v より小さい場合に限ります。同様に、右側の最小値が v より大きければ、右側にあるすべての値が v より大きくなります。2つの小さな再帰ヘルパーで、最大値と最小値をそれぞれ求めます。空の側については、最大値を -1、最小値を 100001 とします。これらは許可された範囲外の値なので、空の側が条件を満たさないことはありません。
これは正しい方法ですが、同じ処理を繰り返します。あるノードは、その上にある祖先ごとに1回ずつ走査されるため、深さが h の木では、訪問回数は合計でおよそ n × h になります。ここでは深さが最大14なので問題ありませんが、n 個のノードが一列に並んだ木では、計算量が O(n²) まで増加します。
アルゴリズム
- 値が
-1ではないすべてのインデックスiを調べます。 2*i+1から始まる左部分木の最大値を見つけます。その位置が空の場合は-1とします。2*i+2から始まる右部分木の最小値を見つけます。その位置が空の場合は100001とします。- 最大値が
tree[i]以上の場合、または最小値がtree[i]以下の場合は、falseを返します。 - 最後のノードの後で、
trueを返します。
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return True中順走査の値は厳密に増加しなければなりません
考え方
中順走査では、左部分木、次にノード、最後に右部分木を訪れます。二分探索木では、この順序は昇順になります。左側のすべての値は小さいため先に来て、右側のすべての値は大きいため後に来るからです。最初の例は 1, 3, 6, 8, 10, 12, 15 となります。
逆も成り立ち、それがこの方法を検査に使える理由です。任意のノード v を考えてみましょう。中順の列では、その左部分木全体が直前に、その右部分木全体が直後に並びます。列が狭義単調増加なら、v より前の値はすべて小さく、後の値はすべて大きいため、v でこの規則が成り立ち、ほかのすべてのノードでも同様に成り立ちます。
そこで、木を中順に走査して値を集め、それぞれの値をひとつ前の値と比較します。2つ目の例は 5, 10, 6, 15, 20 となります。10 から 6 への変化によって、誤った側にあるノードが明らかになります。3つ目は 7, 12, 12 となり、12 の重複は狭義の条件を満たしません。各ノードは一度ずつ訪問されるため、時間計算量は O(n) で、リストには O(n) の領域が必要です。
アルゴリズム
walk(i)を記述します。位置が空なら停止し、そうでなければ2*i+1をたどり、tree[i]を追加してから、2*i+2をたどります。walk(0)を呼び出して、値を順番に収集します。1から始まる各位置kについて、values[k-1] ≥ values[k]ならfalseを返します。trueを返します。
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return True許容範囲を木の下へ伝えていく
考え方
ノードの視点から規則を見てみましょう。各祖先はノードに1つの制限を設けます。値が a の祖先の左部分木にあるノードの値は a より小さくなければならず、右部分木にある場合は a より大きくなければなりません。これらすべての制限を合わせると、1つの開区間 (low, high) になり、ノードの値がその範囲内に厳密に収まるときに限り、ノードは正しい位置にあります。
下へ進むにつれて、その範囲を作ることができます。ルートには制限がありません。値が v のノードから左の子へ進むときは low を維持し、high を v に下げます。右の子へ進むときは high を維持し、low を v に上げます。新しい制限は、置き換える前の制限より常に厳しくなります。これは、v 自身が以前の範囲に対するチェックに合格しているためです。
2つ目の例では、15 に範囲 (10, no limit) が与えられ、それが左の子に (10, 15) として引き継がれます。6 は 10 より小さいため、ほかのノードを見ることなく、そこでチェックに失敗します。値は 0 から 10^5 の間なので、-1 と 100001 を「制限なし」として使います。
処理待ちのノードをそれぞれの範囲とともにスタックに保持します。各ノードは1回だけチェックされ、時間計算量は O(n) です。また、スタックに保持されるのは1つの経路上の処理待ちノードなので、空間計算量は O(h) です。最初に範囲違反が見つかった時点で探索を終了します。
アルゴリズム
(0, -1, 100001)をプッシュします。これはルートのインデックスと、実際の上限がない開区間です。(i, low, high)をポップします。tree[i]がlowとhighの厳密な間にない場合は、falseを返します。- 左の子
2*i+1が実在する場合、範囲(low, tree[i])を指定してプッシュします。 - 右の子
2*i+2が実在する場合、範囲(tree[i], high)を指定してプッシュします。 - スタックが空になったら、
trueを返します。
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
落とし穴と境界ケース
間違った答えの多くは、確認が不十分だったり、正しいものを間違った比較方法で確認したりしています。
- ノードをその子とのみ比較する。
[10, 5, 15, -1, -1, 6, 20]では、親子の組み合わせはどれも正しく見えますが、6は2段上のルートが設定した範囲に違反しています。 - 等しい値を許してしまう。両側の順序は厳密なので、
[12, 7, 12]は有効ではありません。low < v < highとvalues[k-1] < values[k]を使い、≤は使わないでください。 - 親の値だけを下に渡す。左の子には両方の制限が必要です。親より小さく、かつ親が持っていた下限より大きくなければなりません。範囲全体を引き継いでください。
- ノードが取りうる値を「制限なし」の値に選ぶ。値は
0から始まるため、下限を0にすると、[0]のように0を持つ有効なノードを拒否してしまいます。許可されているすべての値より小さい値から始めてください。 - 配列の末尾を越えて読み取る。子を読み取る前に
2*i+1 < tree.lengthを確認し、-1は子がないことを表すものとして扱ってください。 - 配列のインデックスが1から始まるLuaとRで、オフセットを取り違える。
2*i+1の計算ではノードのインデックスを0始まりのままにし、tree[i + 1]を読み取ってください。
よくある質問4
BST を検証する際、各ノードをその子ノードと照合するだけでは不十分なのはなぜですか？
この規則は部分木全体に適用されます。ルートの右部分木の深い位置にあるノードは、たとえはるかに大きなノードの左の子であっても、ルートより大きくなければなりません。[10, 5, 15, -1, -1, 6, 20]では、6は15の左の子としては問題ありませんが、10の右側にあるため、この木は二分探索木ではありません。親だけでなく、すべての祖先からの制限を考慮する必要があります。
二分探索木の検証にかかる時間計算量はどれくらいですか？
標準的な2つの方法である中順チェックと範囲チェックは、どちらも各ノードを1回ずつ調べるため、実行時間は O(n) です。範囲チェックでは、スタック用に O(h) の追加領域が必要です。ここで h は深さです。すべてのノードをその部分木全体と比較する方法もありますが、コストは O(n × h) となり、木がパス状の場合は O(n²) に達します。
すべての値を保存せずに、二分探索木を中順走査で検証できますか？
はい。中順走査のチェックでは、各値を直前の値とだけ比較するため、リストではなく変数に前の値を保持します。再帰または明示的なスタックを使って木を中順にたどり、ある値が前の値より大きくないと分かった時点でfalseを返します。これにより、追加の空間をO(h)に抑えられます。
二分探索木に重複する値を含めることはできますか？
ここで使っている厳密な定義では該当しません。左側の値はすべてより小さく、右側の値はすべてより大きくなければならないため、等しい値が両方に入ることはありません。教科書によっては、たとえば等しい値を右側に置くなど、片側に重複を認める場合があります。そのルールでは、厳密な比較の一方を≤に変更することになるため、判定を書く前に定義を確認してください。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isValidBST(tree):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [8, 3, 12, 1, 6, 10, 15]
期待値
true