首页二叉树的Zig-Zag层序遍历python

二叉树的Zig-Zag层序遍历python

时间: 2025-04-22 10:45:49 浏览: 19

### Python 实现二叉树 Zig-Zag 层序遍历为了实现二叉树的Zig-Zag层序遍历，可以采用广度优先搜索（BFS），并利用双端队列来控制每一层节点访问的方向。下面是一个具体的Python代码示例： ```python from collections import deque, defaultdict 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 = deque([root]) level = 0 while queue: length = len(queue) current_level = deque() for _ in range(length): node = queue.popleft() if level % 2 == 0: current_level.append(node.val) else: current_level.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(list(current_level)) level += 1 return result ``` 此函数`zigzagLevelOrder`接收一个二叉树根节点作为输入参数，并返回按照Zig-Zag顺序排列的结果列表[^1]。 #### 构建测试用例验证上述方法的有效性可以通过创建一棵简单的二叉树来进行测试，如下所示： ```python # 创建测试用例 tree = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7))) print(zigzagLevelOrder(tree)) # 输出应为 [[3], [20, 9], [15, 7]] ``` 通过以上方式实现了对给定二叉树执行Zig-Zag层次遍历的功能。

阅读全文