まず、Zigzagレベル順トラバーサルの原理を説明します。この方法では、通常のレベル順トラバーサルと同様に、キューを使用してノードを管理します。しかし、奇数レベルの場合はノードをキューの前から取り出し、偶数レベルの場合はノードをキューの後ろから取り出します。これにより、交互の順序でノードを訪れることができます。
以下に、シンプルで簡単な方法とコード例を示します。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def zigzagLevelOrder(root):
if not root:
return []
result = []
queue = [root]
level = 1
while queue:
level_nodes = []
size = len(queue)
for _ in range(size):
node = queue.pop(0)
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level % 2 == 0:
level_nodes.reverse()
result.append(level_nodes)
level += 1
return result上記のコードは、二分木のZigzagレベル順トラバーサルを行うための関数zigzagLevelOrderを実装しています。関数は与えられた二分木のルートノードからスタートし、Zigzagレベル順でノードの値を返します。結果はリストとして返されます。
この方法は、キューを使用してノードを管理することで効率的に動作します。奇数レベルの場合はノードをキューの前から取り出し、偶数レベルの場合はノードをキューの後ろから取り出すことで、交互の順序でノードを訪れることができます。
以上が、二分木のZigzagレベル順トラバーサルのシンプルな方法とコード例です。この方法を使うことで、二分木のノードを効率的に訪れることができます。ぜひお試しください。