使用c++回旋打印二叉树的节点

设计一个算法来回旋打印二叉树的节点。这个算法的基本思想是使用层序遍历（广度优先搜索）来访问树的节点，但是在打印时交替改变方向。下面是用C++实现的代码

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 回旋打印二叉树的函数
void spiralOrder(TreeNode* root) {
    if (root == NULL) return;  // 如果树为空，直接返回

    std::queue<TreeNode*> q;  // 用于层序遍历的队列
    q.push(root);  // 将根节点入队

    bool leftToRight = true;  // 控制打印方向的标志
    
    while (!q.empty()) {  // 当队列不为空时继续遍历
        int size = q.size();  // 当前层的节点数
        std::vector<int> level(size);  // 存储当前层的节点值

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();  // 获取队首节点
            q.pop();  // 将节点出队

            // 根据打印方向决定节点在level中的位置
            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);
        }

        // 打印当前层的节点
        for (int val : level) {
            std::cout << val << " ";
        }

        leftToRight = !leftToRight;  // 改变下一层的打印方向
    }
}

// 主函数
int main() {
    // 创建一个示例二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    std::cout << "回旋打印二叉树的结果：" << std::endl;
    spiralOrder(root);

    return 0;
}

这个算法的工作原理如下：

使用队列进行层序遍历（广度优先搜索）。
用一个布尔变量 leftToRight 来控制每一层的打印方向。
对于每一层：
- 创建一个向量 level 来存储当前层的节点值。
- 遍历当前层的所有节点：
  - 如果是从左到右打印，按正常顺序存储到 level。
  - 如果是从右到左打印，按相反顺序存储到 level。
- 将节点的子节点加入队列，为下一层做准备。
- 打印 level 中的所有值。
- 翻转 leftToRight 的值，为下一层改变方向。
重复这个过程，直到队列为空。