103. 二叉树的锯齿形层序遍历

**二叉树的锯齿形层序遍历**

二叉树是一种常见的数据结构，它在计算机科学中有着广泛的应用。二叉树的层序遍历是指从根结点开始，依次访问每个结点的左子树和右子树，直到所有结点都被访问完毕。在本文中，我们将讨论一种特殊的层序遍历方法——锯齿形层序遍历。

**什么是锯齿形层序遍历**

锯齿形层序遍历是一种特殊的层序遍历方法，它遵循以下规则：

1. 从根结点开始，依次访问每个结点的左子树和右子树。
2. 当访问到某个结点时，如果该结点有右子树，则先访问右子树，然后再访问左子树。
3. 如果某个结点没有右子树，则直接访问左子树。

**示例**

为了更好地理解锯齿形层序遍历的概念，我们来看一个简单的例子：

1 / 
23 /  
456

在这个例子中，根结点是1。按照锯齿形层序遍历的规则，我们首先访问左子树（2），然后访问右子树（3）。接着，我们访问左子树（2）的左子树（4）和右子树（5），然后再访问右子树（3）的右子树（6）。

**代码实现**

下面是二叉树的锯齿形层序遍历的代码实现：

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef zigzag_traversal(root):
 if root is None:
 return []

 result = []
 queue = [root]

 while queue:
 level_size = len(queue)
 current_level = []

 for _ in range(level_size):
 node = queue.pop(0)

 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)

 current_level.append(node.value)

 # 如果当前层级是奇数，则反转列表 if level_size %2 !=0:
 current_level.reverse()

 result.extend(current_level)

 return result# 测试代码root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

print(zigzag_traversal(root)) # 输出:[1,3,2,5,4,6]

在这个代码实现中，我们首先定义了一个 `Node` 类来表示二叉树中的结点。然后，我们定义了一个 `zigzag_traversal` 函数来实现锯齿形层序遍历。

在函数内部，我们使用一个队列来存储当前层级的结点。我们首先访问每个结点的左子树和右子树，然后将它们添加到队列中。如果当前层级是奇数，则反转列表以实现锯齿形效果。

最后，我们返回结果列表，包含所有结点的值。

**总结**

二叉树的锯齿形层序遍历是一种特殊的层序遍历方法，它遵循一定规则来访问每个结点。通过使用队列和反转列表，我们可以实现这种遍历方法。在本文中，我们提供了一个示例代码实现，展示了如何在 Python 中实现二叉树的锯齿形层序遍历。