Validate Binary Search Tree
二分木はヒープ順序で配列 tree に格納されています。ルートはインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾に余分な -1 が含まれる場合があります。
二分探索木であれば true を、そうでなければ false を返す isValidBST を記述してください。二分探索木では、各ノードの値は左部分木のすべての値より厳密に大きく、右部分木のすべての値より厳密に小さくなります。
関数
- 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より大きくなければなりません。
- 入力
- tree = [12, 7, 12]
- 出力
- false
- 説明
- ルートの右の子は
12を持ち、ルートと等しい値です。右部分木は厳密に大きくなければならないため、この木は条件を満たしません。
発展問題
ノードの親はインデックス (i-1)/2 にあり、小数点以下は切り捨てます。スタックや再帰の代わりに親をたどりながら、追加の領域 O(1) で木を順番に走査できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
[10, 5, 15, -1, -1, 6, 20]では、すべてのノードが左の子より大きく、右の子より小さくなっています。それでも二分探索木ではないのはなぜでしょうか？すべての祖先ノードは、そのノードに制限を設けます。ノードが祖先の左側にある場合は祖先より小さく、右側にある場合は祖先より大きくなります。これらの制限を合わせると、1つの開区間になります。値
vから左に進むと上限がvに下がり、右に進むと下限がvに上がります。ルートから始め、許容されるすべての値を含む広い範囲を設定して、
(index, low, high)のスタックを保持します。エントリーを取り出し、値が範囲内に厳密に収まっていなければ失敗とし、実際の子ノードそれぞれを範囲を狭めてプッシュします。
解説
この規則は部分木全体に適用されるため、各ノードを2つの子ノードと比較するだけでは不十分です。深い位置にあるノードが、数レベル上の祖先によって設定された上限を破ることがあります。木を順序どおりに読み取って値が厳密に増加していることを確認するか、各ノードに祖先が許容する範囲を渡してください。
各ノードをそのすべての部分木と比較する
考え方
ノードの左側のすべての値がその値 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中順走査の値は厳密に増加しなければなりません
考え方
中順走査では、左部分木、次にノード、最後に右部分木を訪問するため、二分探索木では値がソートされた順に読み取られます。
逆も成り立ちます。任意のノード v について、その左部分木全体は列の中でそのノードの直前に、右部分木全体は直後に並びます。列が厳密に増加していれば、v より前の値はすべて小さく、後の値はすべて大きいため、v でこの規則が成り立ち、すべてのノードでも同様に成り立ちます。
2つ目の例では 5, 10, 6, 15, 20 と読み取られます。10 から 6 への減少によって、誤った位置にあるノードが明らかになります。各ノードは1回ずつ訪問されます。時間計算量は O(n)、リストの空間計算量は O(n) です。
アルゴリズム
walk(i)を記述します。位置が空なら停止し、そうでなければ2*i+1をたどり、tree[i]を追加してから、2*i+2をたどります。walk(0)を呼び出して、値を順番に集めます。- 位置
kを1から順に調べ、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)になり、ノードの値がその範囲内に厳密に収まるときに限り、ノードは正しい位置にあります。
下へ進みながら範囲を作ります。左の子はlowを引き継ぎ、high = vを受け取ります。右の子はhighを引き継ぎ、low = vを受け取ります。2つ目の例では、15は左の子に(10, 15)を渡し、6はその場で条件を満たしません。値は0から10^5の間なので、-1と100001を制限なしとして使います。各ノードは1回ずつチェックされ、時間計算量はO(n)、スタック上のノード数は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がルートの制約に違反します。 - 等しい値を許可する。
[12, 7, 12]は無効です。<で比較し、≤は使わないでください。 - 下限の「制限なし」を表す値として
0を使う。これでは有効な木[0]が拒否されます。 2*i+1 < tree.lengthを確認せずに子ノードを読み取る。[12, 7, 12]では、インデックス3は範囲外です。- LuaとRでは、配列のインデックスは1から始まります。
2*i+1のためにノードのインデックスは0始まりのままにし、tree[i + 1]を読み取ってください。
よくある質問3
二分探索木の検証の時間計算量はどれくらいですか？
中順走査によるチェックと範囲チェックは、それぞれ各ノードを1回ずつ訪問します。時間計算量は O(n) で、深さが h の木における範囲チェックのスタックに必要な追加領域は O(h) です。各ノードをその部分木全体と比較する場合、計算量は O(n × h) となり、道のような形の木では O(n²) に達します。
すべての値を保存せずに、中順走査でBSTが有効かどうかを検証できますか？
はい。このチェックでは各値を直前の値とだけ比較するため、リストではなく変数に前の値を保持し、値が大きくなかった時点でfalseを返します。追加の空間計算量は、再帰またはスタックのためのO(h)に抑えられます。
二分探索木に重複する値を含めることはできますか？
ここで使われている厳密な定義では該当しません。等しい値はどちら側にも入りません。一部の教科書では、たとえば右側に等しい値を許容しています。その規則では、厳密な比較の一方が≤になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isValidBST(tree):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [8, 3, 12, 1, 6, 10, 15]
期待される出力
true