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:

（引用：938. Range Sum of BST）

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）

（引用：LeetCodeを解いて身に付ける木の巡回法）

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 は１回のキューごとに動作するため、各ノードごとに処理が走るため遅いのではないかと考えられます。
（こちらは予想のため、ご指摘あればお願いします。）