之字形打印二叉树算法实现

"之字形打印二叉树的方法和C++代码实现" 在二叉树的遍历中，有一种特殊的方式叫做“之字形”（Zigzag）打印，也称为锯齿形打印。这种遍历方式要求从上至下逐层打印二叉树，但每一层的节点打印顺序是交替的：第一层从左到右，第二层从右到左，第三层再从左到右，以此类推。这种遍历方式在数据结构和算法题目中常见，特别是在面试或编程竞赛中。 给定一个二叉树的根节点，可以使用层次遍历（BFS，广度优先搜索）的方法来实现之字形打印。关键在于跟踪当前遍历的层数以及是否需要反转层内节点的顺序。这里提供了一个C++的解决方案： 首先，定义二叉树的节点结构： ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x): val(x), left(NULL), right(NULL) {} }; ``` 然后，创建一个`Solution`类，包含一个`printFromTopToBottom`成员函数，用于实现之字形打印： ```cpp class Solution { public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { vector<vector<int>> res; if (!root) return res; vector<TreeNode*> level; level.push_back(root); res.push_back(get_val(level)); // 获取第一层的值并添加到结果中 bool zigzag = true; // 记录当前是否需要反转顺序 while (true) { vector<TreeNode*> newLevel; for (auto& u : level) { if (u->left) newLevel.push_back(u->left); // 添加下一层的左子节点 if (u->right) newLevel.push_back(u->right); // 添加下一层的右子节点 } if (newLevel.size()) { // 如果下一层非空 vector<int> temp = get_val(newLevel); // 获取下一层的值 if (zigzag) reverse(temp.begin(), temp.end()); // 反转顺序（如果需要） res.push_back(temp); // 添加到结果中 level = newLevel; // 更新当前层 } else break; // 如果没有更多节点，退出循环 zigzag = !zigzag; // 改变顺序标志 } return res; // 返回结果 } vector<int> get_val(vector<TreeNode*> level) { vector<int> res; for (auto& u : level) res.push_back(u->val); return res; // 获取层内的所有节点值 } }; ``` 在这个实现中，`printFromTopToBottom`函数首先处理根节点所在的层，然后进入一个循环，不断地构建新的层级并检查是否需要反转顺序。当没有更多的节点可遍历时，循环结束。`get_val`辅助函数用于将一层的节点值转换为整型数组。 通过这个方法，我们可以有效地按照之字形顺序打印给定二叉树的各层节点。这个算法的时间复杂度为O(n)，其中n是二叉树中的节点数，因为每个节点都被访问一次。空间复杂度为O(w)，w为树的最大宽度，因为我们需要存储当前层的所有节点。在最坏的情况下，二叉树可能退化成链表，此时宽度最大。