LeetCode - Range Sum of BST をSwiftで解説する
- 元の問題は英語なので、代わりに翻訳したものを記載しています。
- 回答はあくまでも例であり、他の方法も存在します。
前置き
タイトルにある BST とは binary search tree（二分探索木） の略です。
2分探索木とは
2分探索木とは、木構造の探索木のうち、ノードと子ノードにそれぞれ振られた値が「左の子の値は親ノードの値よりも小さい」および「右の子の値は親ノードの値よりも大きい」という関係になっている、すなわち「左の子 ＜ 親ノード ＜ 右の子」という関係が成り立っている探索木のことである。
（引用：2分探索木）
木構造（ツリー構造）とは
ツリー構造とは、データ構造の一種で、ある階層に属する一つのデータから、下位階層に位置する複数のデータが枝分かれした状態で配置されている構造のことである。
（引用：ツリー構造）
問題
| 問題 | 難易度 |
|---|---|
| Range Sum of BST | easy |
二項探索木の root ノードと2つの整数 low と high が与えられたとき
範囲 [low, high] に値を持つ全てのノードの値の総和を返すこと。
補足として、以下のようなテストケースが与えられます。
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
この場合、 7~10 の範囲にある数字の合計は 7 + 10 + 15 = 32 なので、答えは 32 となります。
答え
- 深さ優先探索(DFS)を使用する方法
- 幅優先探索(BFS)を使用する方法
の２つを紹介します。
0. 探索方法に関して
２つは探索のアルゴリズムですが、順番に違いがあります。図で見るのがわかりやすいでしょう。
（引用：DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】）
では、それぞれを詳しく見ていきましょう。
深さ優先探索(DFS)とは
深さ優先探索(DFS)は depth-first search の略で、名前の通り深さを優先した探索方法になります。
深さ優先探索は探索を開始する頂点からの距離（深さ）が離れるように進んでいく方式で、それ以上進めない末端（木の場合は葉ノード、グラフの場合はすべての隣接ノードが探索済みの場合も含む）まで来たら、経路を遡って最初の未探索ノードへ進む。その先で末端に到達したら、再び経路を遡り…という手順を終了まで繰り返す。
(引用：深さ優先探索【DFS】)
つまり、最も深い部分まで探索し、そこから戻っていく探索方法です。さらに、今回のような木構造を探索する場合は、以下のように行きがけ/通りがけ順/帰りがけのパターンがあります。
| 行きがけ順（Preorder） | 通りがけ順（Inorder） | 帰りがけ順（Postorder） |
|---|---|---|
 |
 |
 |
DFS を実装する場合は、再帰関数で実装することができます。
自分自身を呼び出す処理が書かれている関数を呼び出すこと
（引用：再帰処理とは）
幅優先探索(BFS)とは
幅優先探索(BFS) は Breadth-First Search の略で、名前の通り深さを幅を優先した探索方法になります。
幅優先探索は探索を開始する頂点からの距離（深さ）が等しくなるように進んでいく方式で、出発点の隣接ノード（距離1）をすべて調べ、隣接ノードの隣接ノード（距離2）をすべて調べ、そのまた隣接ノード（距離3）を…という手順を終了まで繰り返す。
（引用：幅優先探索【BFS】）
つまり、順番に満遍なく進んでいく探索方法です。
BFS を実装する場合は、キュー を用いて実装することができます。
キューとは、データ構造の一つ（データを格納する入れ物）で、入ってきたデータを順番に格納し、先に格納したデータから順に取り出す、 先入れ先出し（FIFO：First-In First-Out）方式のデータ構造です。
（引用：キュー（queue）とは）
DFS と BFS との比較
ほとんどの問題は、DFS でも BFS で解くこともできます。ただ、問題によっては DFS と BFS で、それぞれ適切な（計算量が少なく高速になる）場合があります。
ざっくり以下のような使い分けがあります。
- DFS: 解がスタートから遠い場合
- BFS: 解がスタートから近い場合
もっとありますが、列挙するとキリがないので、使っていくことで慣れていくと良いでしょう。
1. 深さ優先探索(DFS)を使用する方法
では、再帰関数を使って実装していきましょう。
- 値を返す方法で実装
合計値を返していく方法は、オーソドックスな方法でしょう。他の言語で実装する場合も同じように書くことができるので、パターンを覚えておいても損はないと思います。
例は帰りがけ順で実装しています。
func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
guard let n = root else { return 0 }
// 値が範囲の中にあるのか探す
var sum = (low...high).contains(n.val) ? n.val : 0
// 左側を探索
sum += rangeSumBST(n.left, low, high)
// 右側を探索
sum += rangeSumBST(n.right, low, high)
// 合計値を返す
return sum
}
ちなみに
(low...high).contains(n.val) ? n.val : 0
をsumに加算するタイミングを移動することで、通りがけ順や帰りがけ順に書き換えが可能です。
- inout で実装
Swift の特有の inout を使用して合計値を足していく方法でも実装できます。各言語によって参照型の書き方は変わるので、書き方はSwift 独自の方法だと思っておいてください。
例は行きがけ順で実装しています。
func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
var sum = 0
dfs(root, low, high, sum: &sum)
return sum
}
func dfs(_ node: TreeNode?, _ low: Int, _ high: Int, sum: inout Int) {
guard let n = node else { return }
// 値が範囲の中にあるのか探した、足していく
sum += (low...high).contains(n.val) ? n.val : 0
// 左側を探索
dfs(n.left, low, high, sum: &sum)
// 右側を探索
dfs(n.right, low, high, sum: &sum)
}
ちなみに先ほどと同様に
sum += (low...high).contains(n.val) ? n.val : 0
の位置を変えることで、通りがけ順や帰りがけ順に書き換えが可能です。
2. 幅優先探索(BFS)を使用する方法
では、キューを使って実装していきましょう。
func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
guard let r = root else { return 0 }
// キューを保管する場所
var queues = [r]
// 合計値を足していく
var sum = 0
// キューがなくなるまで処理を継続する
while !queues.isEmpty {
// 先頭のキューを取り出す
let queue = queues.removeFirst()
// 範囲内に値か判定する
sum += (low...high).contains(queue.val) ? queue.val : 0
// 左側がある場合は次のキューに追加する
if let l = queue.left {
queues.append(l)
}
// 右側がある場合は次のキューに追加する
if let r = queue.right {
queues.append(r)
}
}
return sum
}
実行結果
| Kind | Runtime | Memory |
|---|---|---|
| DFS | 500ms~ | 16MB前後 |
| BFS | 600~1400ms | 16MB前後 |
考察
今回の問題は全探索のため、計算量は同じです。なので速度に差が出ないはずですが、DFS の方が早いようです。
どうやら DFS の場合は、１回の処理に対して並列で動いているように思います。一方の BFS は１回のキューごとに動作するため、各ノードごとに処理が走るため遅いのではないかと考えられます。
（こちらは予想のため、ご指摘あればお願いします。）
Discussion