给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路：
使用 BFS（广度优先搜索）算法，但在遍历每一层时，根据当前层的奇偶性来决定节点值的输出顺序。

#include <vector>
#include <queue>
#include <iostream>using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) return result;queue<TreeNode*> q;q.push(root);bool leftToRight = true; // 控制遍历顺序while (!q.empty()) {int size = q.size();vector<int> level(size);for (int i = 0; i < size; ++i) {TreeNode* node = q.front();q.pop();// 根据遍历顺序确定节点值的插入位置int index = leftToRight ? i : size - 1 - i;level[index] = node->val;if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(level);leftToRight = !leftToRight; // 切换遍历顺序}return result;}
};// 辅助函数：释放二叉树节点内存
void deleteTree(TreeNode* root) {if (!root) return;deleteTree(root->left);deleteTree(root->right);delete root;
}int main() {// 创建二叉树TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);// 创建解决方案对象Solution solution;// 获取锯齿形层序遍历结果vector<vector<int>> result = solution.zigzagLevelOrder(root);// 输出结果cout << "Zigzag level order traversal: " << endl;for (const auto& level : result) {for (int val : level) {cout << val << " ";}cout << endl;}// 释放内存deleteTree(root);return 0;
}

这个算法的时间复杂度取决于二叉树的节点数量，假设节点总数为 ( n )。在算法中，我们通过 BFS 遍历了整棵二叉树，每个节点只会被访问一次，因此时间复杂度为 ( O(n) )。

空间复杂度主要由队列和结果数组所占用的空间决定。在最坏情况下，队列中会存储二叉树的所有叶子节点，而二叉树的叶子节点数量最多为 ( n/2 )，因此队列的空间复杂度为 ( O(n) )。此外，结果数组所需的空间与二叉树的高度成正比，最坏情况下为 ( O(log n) )。因此，总的空间复杂度为 ( O(n) )。