使用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;
}

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

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

这个算法的时间复杂度是 O(n)，其中 n 是树中节点的数量，因为每个节点都被访问一次。空间复杂度也是 O(n)，主要是由队列和存储每一层节点的向量所占用的空间决定的。