バイナリツリー_レベルオーダー走査(Level Order Traversal)　#444

ゆーき|YM202110

2024年1月21日 11:29

バイナリツリーの走査方法の第4弾です。
バイナリツリーについて別で4本記事を書いています。

走査とは先頭から順にデータを見ていくことを指し、バイナリツリーを走査するアルゴリズムは主に４つあります。

Pre-order Traversal
In-order Traversal
Post-order Traversal
Level-order Traversal

このうちのLevel-order Traversalについてです。

レベルオーダー走査とは

今回の幅優先探索（BFS：Breadth-First Search）またはレベルオーダー走査は、バイナリツリーをレベル別に探索する方法です。この探索方法では、ツリーの各レベルを順番に、左から右へとノードを訪問します。

参考ブログに分かりやすい図がありました。

幅優先探索での走査は、深さ優先探索のように再帰を用いたプログラムでは表現できないので「キュー」というデータ構造を使って表現します。

大雑把には以下の手順で処理が進みます。

訪問するノードを保持するキュー（先入れ先出し）を使用する
ルートノードをキューに入れる
キューの要素数(=そのレベルの数)を取得してforループ
ルートノードの処理をする
ルートノードの左右の子ノードをキューに追加する
最初は1回でforループ終わり
キューの要素数(=次のレベルの数)を取得してforループ
左ノードの処理をして、その左右の子ノードをキューに追加する
右ノードの処理をして、その左右の子ノードをキューに追加する
キューの要素数(=次のレベルの数)を取得してforループ
左ノードの処理をして……

forループを何度も回すのですが、開始時点でのqueueの数（=そのレベルの要素数）を取得しておき、その数だけループさせます。そうすることで、queuに次のレベルの情報を順次格納しつつ、各レベル単位で処理ができます。

つまり以下のようなバイナリツリーがあった場合、

queuの状態は以下のように推移します。

ステップ1: ルートノードをキューに挿入

キューの状態: [1]
処理するノード: 1

ステップ2: ノード1の子ノードをキューに挿入

キューの状態: [2, 3]
処理するノード: 2, 3

ステップ3: ノード2の子ノードをキューに挿入

キューの状態: [3, 4, 5]
処理するノード: 3

ステップ4: ノード3の子ノードがないため、キューは変化なし

キューの状態: [4, 5]
処理するノード: 4, 5

具体的なコード例

ライブラリなどを使わずにPythonで実装すると以下のようになります。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            level = []
            
            for _ in range(level_size):
                print(level_size)
                node = queue.pop(0)
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(level)
        
        return result

leetcodeで上記のコードを実行した場合、以下のパフォーマンスでした。

35 / 35 test cases passed.

Runtime: 42 ms
Memory Usage: 17.2 MB

Pythonのcollectionsライブラリでは、キューを扱うためのdequeメソッドが存在するので、そちらを使って同じことをやってみます。キューを入れるところと、先頭のノードを取り出すところの処理を少し編集しています。

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(level)
        
        return result

今回の処理ではパフォーマンスはあまり変わりませんでした。


35 / 35 test cases passed.

Runtime: 40 ms
Memory Usage: 17.2 MB

ここまでお読みいただきありがとうございました！

バイナリツリー_レベルオーダー走査(Level Order Traversal) #444