剑指offer59:按之字形顺序打印二叉树:[[1], [3,2], [4,5,6,7]]
2024-08-27 00:59:23
1 题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
2 思路和方法
先给定一个二叉树的样式:
输出的样式是:[[1], [3,2], [4,5,6,7]]。包含以下信息: (1)每一层所包含的树节点;(2)偶数层的树节点需倒序。
思路: 面对要求的偶数层倒序,亦有两种解题思路,第一种是:获取到所有节点的值后,将偶数层的节点值倒序(先存right,再存left实现倒序)。第二种则是在获取节点的值的时候就倒序存入。定义两堆栈stack1和stack2,在遍历当前层节点的同时!stack1.empty() TreeNode *data=stack1.top();,存储下一层的节点(stack2.push(data->right),stack2.push(data->left)),以此类推,!stack2.empty() TreeNode *data=stack2.top();,存储下一层的节点(stack1.push(data->left),stack2.push(data->right))。
3 C++核心代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> result;
if(pRoot==nullptr)
return result;
stack<TreeNode*> stack1,stack2;//分别存奇数和偶数层
stack1.push(pRoot);
while(!stack1.empty() || !stack2.empty()){
if(!stack1.empty()){
vector<int> temp;
while(!stack1.empty()){
TreeNode *data=stack1.top();
stack1.pop();
temp.push_back(data->val);
if(data->left!=nullptr)
stack2.push(data->left);
if(data->right!=nullptr)
stack2.push(data->right);
}
result.push_back(temp);
}
if(!stack2.empty()){
vector<int> temp;
while(!stack2.empty()){
TreeNode *data=stack2.top();
stack2.pop();
temp.push_back(data->val);
if(data->right!=nullptr)
stack1.push(data->right);
if(data->left!=nullptr)
stack1.push(data->left);
}
result.push_back(temp);
}
}
return result;
}
};
参考资料
https://blog.csdn.net/u010005281/article/details/79759926
最新文章
- DataTable扩展方法ToList<;T>;()、ToJSON()、ToArrayList()
- 一天一小段js代码(no.1)
- error C3861: “LOG4CPLUS_DEBUG”: 找不到标识
- Android:控件GridView的使用
- eclipse和cygwin搭建C++环境的修正版本
- GCC使用
- IE6存在的一些兼容
- unity3d 各功能的运行秩序,打回来,订购,的次数
- linux处置服务Iptables
- JavaScript中typeof,instanceof,hasOwnProperty,in的用法和区别
- java的数组
- Celery提交任务出错?
- Vue-cli添加全局js
- struts2框架学习笔记2:配置详解
- ecshop首页调用团购信息产品购买人数
- springBoot 学习(总)
- npm安装第三方库找不到“cl.exe”问题
- ruby on rails在fedora18上install
- 自己定义View时,用到Paint Canvas的一些温故,简单的帧动画(动画一 ,&;quot;掏粪男孩Gif&;quot;顺便再提提onWindowFocusChanged)
- Hive-查询结果导入到 MySQL
热门文章
- html5的figure/figcaption讲解及实例
- Oracle审计表AUD$处理方法
- laravel修改了配置文件不生效,修改了数据库配置文件不生效
- TP5.1框架最后登录时间不会更新
- cv2.imread()
- windows mysql绿色版配置Mysql5.7.X
- Docker 记一次 docker-compose 完整实践(转)
- 安装DEDECMS出现Function ereg_replace()错误的解决方法
- error C1002: 在第 2 遍中编译器的堆空间不足
- osg编译日志