TreeNodeクラスとレベル順BFS
配列から二分木を構築し、dequeによるBFSでレベルごとに出力し、BFSを使ってmaximum-depthを解きます。
「TreeNodeクラスとレベル順BFS」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
TreeNodeクラスの基礎
二分木は、各ノードが左と右と呼ばれる最大 2 つの子を持つ階層型データ構造です。Python では、単純なクラスを使ってノードをモデル化します。class TreeNode: def __init__(self, val=0, left=None, right=None)。面接で出題される木の問題はすべてこの定義から始まり、ほぼすべての LeetCode の木の問題のボイラープレートでこの定義を目にすることになります。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)配列から木を構築する
面接問題では、None が欠落したノードを表すレベル順配列として木が与えられることがよくあります。インデックス i の場合、左の子は 2i+1、右の子は 2i+2 にあります。この配列を参照でつながった TreeNode にデシリアライズするヘルパーを書くと、練習中に時間を節約できる便利なユーティリティになります。
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)BFSとは何か、なぜキューなのか
幅優先探索（BFS）は、深さ d のすべてのノードを訪問してから、深さ d+1 のノードを訪問します。このレベルごとの走査は、キュー（FIFO）が提供する処理そのものです。まずルートをキューに追加し、ノードを 1 つずつ処理しながら、それぞれの子をキューに追加します。Python の collections.deque は appendleft と popleft を O(1) で実行できるため、通常のリストより適しています。
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4レベル順BFS：レベルごとのグループ化
標準的な BFS の応用では、各反復の開始時点でのキューのサイズを記録して、ノードをレベルごとにグループ化します。その数のノードだけを正確に処理して値を集め、次のレベルへ進みます。これによりリストのリストが生成されます。これは、二分木のレベル順走査、ジグザグ走査、右側面図などの問題で非常によく使われる面接の出力形式です。
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]BFSによる最大深度
二分木の最大深度は、BFS の走査におけるレベル数と等しくなります。レベルを処理するループを何回完了したかを数えるだけです。これにより、時間計算量 O(n)、空間計算量 O(w) の解法になります。ここで w は木の最大幅です。平衡木では w は O(n/2) なので、最悪時の空間計算量は O(n) です。
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3二分木の右側面図
右側面図は、木を右から見たときに見える最後のノード、つまり BFS の走査における各レベルの最後の要素を返します。これはレベル順 BFS を直接適用したものです。各レベルのループで最後のノードを集めます。時間計算量は O(n)、キューに必要な空間計算量は O(w) です。
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]ジグザグ順のレベル走査
ジグザグ走査では、奇数レベルを左から右へ、偶数レベルを右から左へ収集します。最もすっきりした実装では、BFSのキューは変更せず、結果に追加する前にレベルごとのリストを交互に反転します。各レベルで反転する向きをブール型のフラグで管理します。これにより、内部ループで両端キューを扱う複雑さを避けられます。
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))BFSの空間計算量分析
BFSが使用する空間計算量はO(w)です。ここでwは木の最大幅です。完全二分木のノード数をnとすると、最後のレベルには(n+1)/2個のノードがあります。つまり、BFSのキューには最大でn/2個のノードを同時に保持することになります。そのため、幅の広い平衡木では、BFSの空間計算量はDFS（O(h)）より大きくなります。一方、深く偏った木では、DFSの呼び出しスタックの深さがnになるため、BFSのほうが優れています。
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')二分木の各レベルの平均値
各レベルの平均値を計算するのも、BFSを直接応用した例です。あるレベルのすべての値を合計し、要素数で割って結果リストに追加します。この問題では、レベルのループ内で算術演算を行えるかが問われます。Python 3では必ずfloat除算（/演算子）を使用し、最初に空の木の場合も処理してください。
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]BFSによる最小深さ
最小深さとは、根から最も近い葉ノード（子を持たないノード）までの距離です。BFSを使うと最適に求められます。レベル順走査で最初に見つかる葉ノードは、必ず最小深さにあります。葉に到達したら、現在の深さをすぐに返します。最悪の場合はO(n)ですが、平衡木では多くの場合、より早く終了します。
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2レベル順の兄弟ノードを接続する
next-rightポインタの設定問題では、各ノードを同じレベルの右隣のノードに接続します。BFSを使えば簡単です。各レベルのループ内で、最後のノード以外についてnode.next = q[0]を設定します。これは、BFSなら解法が明快になる一方、DFSでは部分木をまたいだポインタを慎重に追跡する必要がある典型的な例です。
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、TreeNodeクラスの定義と配列から木を構築する方法、レベルサイズのテクニックでノードをグループ化するdequeを使ったレベル順BFS、そして最大深さ、最小深さ、右側から見たビュー、ジグザグ走査、各レベルの平均値などの応用例を学びました。次は、再帰的なDFSの走査順序について学びます。
よくある質問
「TreeNodeクラスとレベル順BFS」レッスンは無料ですか？
はい。「TreeNodeクラスとレベル順BFS」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「TreeNodeクラスとレベル順BFS」で何を学びますか？
配列から二分木を構築し、dequeによるBFSでレベルごとに出力し、BFSを使ってmaximum-depthを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「TreeNodeクラスとレベル順BFS」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- TreeNodeクラスとレベル順BFS
- in-order、pre-order、post-order DFS
- 直径、高さ、平衡木
- パスの合計と最近共通祖先