之字形打印二叉树算法实现
版权申诉
199 浏览量
更新于2024-08-31
收藏 2KB MD 举报
"之字形打印二叉树的方法和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为树的最大宽度,因为我们需要存储当前层的所有节点。在最坏的情况下,二叉树可能退化成链表,此时宽度最大。
Roc-xb
- 粉丝: 13w+
- 资源: 7849
最新资源
- 新代数控API接口实现CNC数据采集技术解析
- Java版Window任务管理器的设计与实现
- 响应式网页模板及前端源码合集:HTML、CSS、JS与H5
- 可爱贪吃蛇动画特效的Canvas实现教程
- 微信小程序婚礼邀请函教程
- SOCR UCLA WebGis修改:整合世界银行数据
- BUPT计网课程设计:实现具有中继转发功能的DNS服务器
- C# Winform记事本工具开发教程与功能介绍
- 移动端自适应H5网页模板与前端源码包
- Logadm日志管理工具:创建与删除日志条目的详细指南
- 双日记微信小程序开源项目-百度地图集成
- ThreeJS天空盒素材集锦 35+ 优质效果
- 百度地图Java源码深度解析:GoogleDapper中文翻译与应用
- Linux系统调查工具:BashScripts脚本集合
- Kubernetes v1.20 完整二进制安装指南与脚本
- 百度地图开发java源码-KSYMediaPlayerKit_Android库更新与使用说明