Range Sum of BST
二分探索木がレベル順に配列 tree に格納されており、2つの数値 low と high が与えられます。ルートはインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾には余分な -1 が含まれる場合があります。二分探索木では、ノードの左部分木にあるすべての値はそのノードの値より小さく、右部分木にあるすべての値は大きくなります。
rangeSumBST という名前の関数を作成し、low ≤ v ≤ high を満たすすべてのノード値 v の合計を返してください。その範囲内に値がない場合は 0 を返します。
関数
- treeinteger-array
- 二分探索木をレベル順で表し、空の位置には -1 を使用します
- lowinteger
- カウントする最小値
- highinteger
- カウントする最大値
- 戻り値integer
- lowとhighの間にあるノードの値の合計（lowとhighを含む）
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1または0 ≤ tree[i] ≤ 105を満たす値です。 tree[0]が-1になることはないため、木には少なくとも1つのノードがあります。- 配列は、最後のノードより後に余分な
-1の要素が含まれている場合があります。 - 空の位置の子は両方とも空で、深さは最大でも
14です。 - この木は有効な二分探索木なので、すべての値は異なります。
0 ≤ low ≤ high ≤ 105- 答えは32ビット符号付き整数に収まります。
例
- 入力
- tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
- 出力
- 88
- 説明
9から31までの値は10、12、15、20、31で、合計は88です。3、8、40は範囲外です。
- 入力
- tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
- 出力
- 0
- 説明
- この木には
25、50、75があり、そのどれも60から70の間にないため、合計は0です。4つの-1は、25と75の空の子ノードの位置です。
- 入力
- tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
- 出力
- 4
- 説明
lowとhighがどちらも4の場合、値が4のノードだけが対象になります。インデックス4の4は2の右の子なので、答えは4です。
提出時に隠しテスト+14件
発展問題
同じ木に対して異なる(low, high)のクエリに何千回も答える必要があるとしたら、それぞれにO(log n)時間で答えるにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべてのノードを訪問し、範囲内の値を加算すれば正しい答えが得られます。探索木の順序から、あるノードの下にある値について何がわかりますか？
ノードの左部分木にあるものはすべてそのノードより小さく、右部分木にあるものはすべて大きくなります。ノードの値が
low以下の場合、その左側に範囲内のものはあり得るでしょうか？ルートからインデックスのスタックを使って木をたどります。ノードの値が範囲内にある場合はその値を加算し、値が
lowより大きい場合にのみ左の子を2*i+1に、値がhighより小さい場合にのみ右の子を2*i+2に追加します。
解説
範囲内のすべての値を合計するのは、単純な走査です。各ノードを訪れ、条件に合うものを残します。探索木の順序を利用すれば、より効率よくできます。ノードの値から、小さい値と大きい値がどちら側にあるかがわかるため、部分木の中のノードを一つも調べずに、部分木全体をスキップできます。
すべてのノードを訪問する
考え方
まず、配列内の移動方法を見てみましょう。インデックス i のノードは、左の子が 2*i+1、右の子が 2*i+2 にあります。子ノードが実在するのは、そのインデックスが配列内にあり、そこにある値が -1 ではない場合だけです。[20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] では、ルート 20 の子である 8 と 31 はインデックス 1 と 2 にあり、インデックス 4 の 12 の子である 10 と 15 はインデックス 9 と 10 にあります。また、31 の左側はインデックス 5 で空です。
次に、考え方です。範囲内の値はすべていずれかのノードにあるため、すべてのノードを訪れて、low ≤ v ≤ high を満たす値を加算する走査を行えば、正しい合計が得られます。ノードのインデックスを格納するスタックを使います。ルートから始め、インデックスを取り出し、その値が範囲内なら加算して、実在する子ノードをそれぞれスタックに追加します。
この方法は二分探索木の性質をまったく利用せず、どんな二分木にも使えます。n 個のノードすべてに触れるため、時間計算量は O(n) です。スタックには、ある経路に沿った未処理の子ノードが格納されるため、深さを h とすると、空間計算量は O(h) です。数千個のノードがある木で、範囲内の値がわずかしかない場合、その作業のほとんどは無駄になります。
アルゴリズム
- ルートのインデックス
0をスタックにプッシュし、total = 0を設定します。 - インデックス
iをポップします。low ≤ tree[i] ≤ highの場合、tree[i]をtotalに加算します。 - 配列の範囲内にあり、
-1ではない場合、2*i+1と2*i+2をプッシュします。 - スタックが空になったら、
totalを返します。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append(left)
if right < n and tree[right] != -1:
stack.append(right)
return total探索木の順序で枝刈りする
考え方
同じスタック走査を使いますが、順序を利用します。ノードが v を持つとします。その左部分木には v より小さい値だけが含まれます。v ≤ low なら、それらはすべて low より小さいため、左部分木から追加される値はありません。つまり、左部分木をスキップします。同様に、v ≥ high なら、右部分木には high より大きい値だけが含まれるため、右部分木をスキップします。したがって、左の子をプッシュするのは v > low の場合だけ、右の子をプッシュするのは v < high の場合だけです。
範囲 [9, 31] の最初の例では、31 は high と等しいため、その右の子 40 はプッシュされません。8 は low より小さいので、その左の子 3 はスキップされます。一方、8 と 20 の間の値は範囲内にある可能性があるため、右の子 12 は引き続き訪問されます。
訪問するノードは、範囲内の k 個の値と、その範囲の端に沿ったルートから葉までのパス最大2本分なので、時間計算量は O(h + k) です。範囲が木全体を含む場合は依然として O(n) ですが、大きな木でも狭い範囲なら、訪問するノードは数十個だけです。スタックに必要な空間は O(h) です。
アルゴリズム
- ルートのインデックス
0をスタックにプッシュし、total = 0に設定します。 - インデックス
iをポップし、v = tree[i]を読み取ります。low ≤ v ≤ highの場合、vをtotalに加算します。 v > lowの場合、左の子2*i+1が実在すればプッシュします。v < highの場合、右の子2*i+2が実在すればプッシュします。- スタックが空になったら、
totalを返します。
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
# Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
if value > low and left < n and tree[left] != -1:
stack.append(left)
if value < high and right < n and tree[right] != -1:
stack.append(right)
return total
落とし穴と境界ケース
誤答の多くは、範囲または配列の境界が原因です。
- 厳密な比較を使うこと。範囲の両端は含まれるため、
lowまたはhighと等しいノードも該当します。 - 枝刈りが1段階早すぎること。
vがlowと等しい場合は左部分木をスキップできますが、vがlow + 1の場合はできません。そこにはlow自体が含まれている可能性があります。 - 範囲外のノードで探索を止めること。
lowより小さいノードでも、右部分木には範囲内の値がすべて含まれている可能性があるため、順序の規則によって除外できる側だけをスキップします。 - 配列の末尾を越えて子のインデックスを読み取ること。値を読み取る前に
2*i+1 < tree.lengthを確認し、-1は子がないことを示す値として扱います。 - 配列のインデックスが1から始まるLuaとRで、オフセットを混同すること。
2*i+1の計算ではノードのインデックスを0始まりのままにし、tree[i + 1]を読み取ります。
よくある質問4
BSTの範囲合計の時間計算量はどれくらいですか？
二分探索木の順序を利用して枝刈りする走査では、範囲内のk個のノードに加えて、根からの最大2本の経路上にあるノードを訪問します。深さhの木の場合、時間計算量はO(h + k)です。最悪の場合、すべての値が範囲内にあるときはO(n)です。追加の空間計算量は、スタックまたは再帰のためのO(h)です。
BSTの範囲合計では、なぜ部分木をスキップできるのでしょうか？
二分探索木では、ノードの左側にある値はすべてそのノードの値より小さく、右側にある値はすべて大きくなります。ノードの値が low 以下なら、その左側に範囲内に入る値はなく、high 以上なら、その右側にもありません。それらの側をスキップしても、範囲内の値を見落とすことはありません。
BSTの範囲合計は、中順走査で解けますか？
はい。二分探索木の中順走査では値が昇順に並ぶため、lowに達した値を加算し、highを超えた時点ですぐに停止できます。同じ答えが得られ、早期停止によって木の右側での処理を省けます。一方、枝刈りを行う探索では左側での処理も省けます。
BSTの範囲合計には、再帰とスタックのどちらを使うべきでしょうか？
どちらも機能します。再帰のほうが短く、ここでは深さが最大でも14なので、コールスタックは小さく保たれます。明示的なスタックを使えば再帰の上限を完全に回避できるため、数千レベルある高い木では重要です。また、このページの解答では明示的なスタックを使っています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def rangeSumBST(tree, low, high):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
期待値
88