"二叉树的锯齿形层序遍历算法实现"
二叉树的锯齿形层序遍历是一种特殊的二叉树遍历方法,它结合了层次遍历(广度优先搜索)和交替左右节点的顺序。在层次遍历的基础上,每一层的节点按照从左到右,然后从右到左的顺序交替进行。这种遍历方式在处理二叉树的某些问题时非常有用,如打印二叉树的特定视图。
给定的题目要求返回一个二叉树的锯齿形层序遍历结果,例如对于以下二叉树:
```
3
/ \
9 20
/ \
15 7
```
其锯齿形层序遍历的结果为:
```
[
[3],
[20, 9],
[15, 7]
]
```
这里给出的C++代码实现了一个名为`Solution`的类,其中包含一个名为`zigzagLevelOrder`的成员函数,用于完成锯齿形层序遍历。以下是该函数的详细解释:
1. `zigzagLevelOrder`函数接受一个指向二叉树根节点的指针`TreeNode* root`作为输入。
2. 定义一个二维整数向量`ans`,用于存储遍历结果。
3. 如果根节点为空,直接返回空向量`ans`。
4. 使用队列`queue<TreeNode*> nodeQueue`来实现层次遍历,初始将根节点入队。
5. 定义一个布尔变量`isOrderLeft`,用于标记当前层是按从左到右还是从右到左的顺序添加节点值。初始设置为`true`,表示从左到右。
6. 当队列不为空时,执行以下操作:
- 创建一个双端队列`deque<int> levelList`,用于存储当前层的节点值。
- 获取当前层的节点数量`size`。
- 遍历当前层的每个节点:
- 弹出队列中的第一个节点`node`,根据`isOrderLeft`的值决定将其值添加到`levelList`的前端或后端。
- 如果节点有左孩子,将其左孩子入队。
- 如果节点有右孩子,将其右孩子入队。
- 将`levelList`转换为普通向量并添加到`ans`中,以保存当前层的节点值。
- 反转`isOrderLeft`的值,切换下一层的添加顺序。
7. 遍历完成后,返回二维向量`ans`,它包含了二叉树的锯齿形层序遍历结果。
这段代码提供了一种简洁且有效的解决方案,通过队列和双端队列的结合,实现了二叉树的锯齿形层序遍历。在实际编程中,这种技巧可以应用于处理类似问题,例如打印二叉树的不同视图或进行其他基于层次的遍历操作。