二叉树锯齿形层序遍历算法实现

"二叉树的锯齿形层序遍历算法实现" 二叉树的锯齿形层序遍历是一种特殊的二叉树遍历方法，它结合了层次遍历（广度优先搜索）和交替左右节点的顺序。在层次遍历的基础上，每一层的节点按照从左到右，然后从右到左的顺序交替进行。这种遍历方式在处理二叉树的某些问题时非常有用，如打印二叉树的特定视图。 给定的题目要求返回一个二叉树的锯齿形层序遍历结果，例如对于以下二叉树： ``` 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`，它包含了二叉树的锯齿形层序遍历结果。 这段代码提供了一种简洁且有效的解决方案，通过队列和双端队列的结合，实现了二叉树的锯齿形层序遍历。在实际编程中，这种技巧可以应用于处理类似问题，例如打印二叉树的不同视图或进行其他基于层次的遍历操作。