剑指offer 面试题. 按之字形顺序打印二叉树
2024-09-01 23:20:46
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
方法1：
正常层次遍历，利用普通队列。逢奇数行（从0算起）就把该层结果逆序。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
if(pRoot==nullptr){return {};}
queue<TreeNode*> my_queue;
my_queue.push(pRoot);
vector<vector<int>>res;
vector<int> vec;
int cnt=;
while(not my_queue.empty()){
vec.clear();
int cur_siz=my_queue.size();
for(int i=;i<cur_siz;++i){
auto cur=my_queue.front();
my_queue.pop();
vec.push_back(cur->val);
if(cur->left){
my_queue.push(cur->left);
}
if(cur->right){
my_queue.push(cur->right);
}
}
if(cnt&){
reverse(vec.begin(),vec.end());
}
res.push_back(vec);
++cnt;
}
return res;
}
};
方法2：
利用双端队列，队列中顺序始终是正常的，但奇数行从右向左遍历，pop右边的，孩子push进左边。偶数行从左向右遍历，pop左边的，孩子push进右边。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
if(pRoot==nullptr){return {};}
deque<TreeNode*> my_queue;
my_queue.push_back(pRoot);
vector<vector<int>>res;
int cnt=;
while(not my_queue.empty()){
res.push_back({});
int cur_siz=my_queue.size();
decltype(pRoot) cur;
for(int i=;i<cur_siz;++i){
if(cnt&){
cur=my_queue.back();
my_queue.pop_back();
if(cur->right){
my_queue.push_front(cur->right);
}
if(cur->left){
my_queue.push_front(cur->left);
}
}
else{
cur=my_queue.front();
my_queue.pop_front();
if(cur->left){
my_queue.push_back(cur->left);
}
if(cur->right){
my_queue.push_back(cur->right);
}
}
res.back().push_back(cur->val);
}
++cnt;
}
return res;
}
};
最新文章
- Dapper学习笔记（2）-链接引用
- TCPCopy使用
- mysql语句 索引操作
- 【LeetCode】257. Binary Tree Paths
- 自己实现的库函数2（memset,memcmp,memcpy,memmove）
- IMAP与POP3的区别
- 进阶：案例六: Context Menu(静态 与 动态)
- 使用zzip和minizip解压缩文件
- MySQL之查询优化方式（笔记）
- 解题的小问题（C++）
- 【LeetCode】87. Scramble String
- Spark算子--map和flatMap
- [LeetCode] K Empty Slots K个空槽
- 在Winform开发框架中下拉列表绑定字典以及使用缓存提高界面显示速度
- 人生苦短,我用python(目录)
- 第八周学习笔记-ADO.Net中DataTable的应用
- java学习--java源文件
- oracle 执行顺序 select查询优化
- 8.2 DRAM和SRAM
- mysql数据库备份shell