まず、再帰を使用したレベル順トラバーサルのアルゴリズムを見てみましょう。以下は、再帰関数を使用してレベル順トラバーサルを実装する例です。
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def level_order_traversal(root):
if root is None:
return
height = get_height(root)
for level in range(1, height+1):
print_level(root, level)
def get_height(node):
if node is None:
return 0
else:
left_height = get_height(node.left)
right_height = get_height(node.right)
return max(left_height, right_height) + 1
def print_level(node, level):
if node is None:
return
if level == 1:
print(node.val)
elif level > 1:
print_level(node.left, level-1)
print_level(node.right, level-1)このコードでは、再帰関数 level_order_traversal が与えられた二分木の高さを計算し、各レベルごとに print_level 関数を呼び出してノードの値を出力します。
-
グローバルリストを使用する:
print_level関数では、ノードの値を直接出力する代わりに、グローバルリストに結果を格納します。これにより、再帰呼び出しの間で値を保持できます。 -
キューを使用する: 再帰を使用せずにレベル順トラバーサルを実装する方法として、キューを使用する方法もあります。キューに根ノードを追加し、キューが空になるまで以下の手順を繰り返します。
- キューからノードを取り出し、その値を出力します。
- 左の子ノードと右の子ノードをキューに追加します。
これらの解決策を用いた改善版のコードを以下に示します。
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def level_order_traversal(root):
if root is None:
return
queue = []
queue.append(root)
while len(queue) > 0:
node = queue.pop(0)
print(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)この改善版のコードでは、グローバルリストや再帰呼び出しを使用せずに、キューを使用して効果的にレベル順トラバーサルを実装しています。