LeetCode 103——二叉树的锯齿形层次遍历
2024-09-05 21:18:26
1. 题目
2. 解答
定义两个栈 s_l_r、s_r_l 分别负责从左到右和从右到左遍历某一层的节点,用标志变量 flag 来控制具体情况,根节点所在层 flag=1 表示从左到右遍历,每隔一层改变一次遍历方向。
用栈 s_l_r 从左到右遍历当前层节点时,按照先左子节点再右子节点的顺序将这一层节点的子节点依次放入栈 s_r_l 中。
用栈 s_r_l 从右到左遍历当前层节点时,按照先右子节点再左子节点的顺序将这一层节点的子节点依次放入栈 s_l_r 中。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
vector<int> temp;
stack<TreeNode *> s_l_r;
stack<TreeNode *> s_r_l;
if (root) s_l_r.push(root);
int flag = 1;
// 根节点层从左往右遍历,然后每隔一层改变遍历方向
while (!s_l_r.empty() || !s_r_l.empty())
{
if (flag)
{
while (!s_l_r.empty())
{
TreeNode * cur = s_l_r.top();
s_l_r.pop();
temp.push_back(cur->val);
if (cur->left) s_r_l.push(cur->left);
if (cur->right) s_r_l.push(cur->right);
}
}
else
{
while (!s_r_l.empty())
{
TreeNode * cur = s_r_l.top();
s_r_l.pop();
temp.push_back(cur->val);
if (cur->right) s_l_r.push(cur->right);
if (cur->left) s_l_r.push(cur->left);
}
}
flag = 1 - flag;
result.push_back(temp);
temp.clear();
}
return result;
}
};
获取更多精彩,请关注「seniusen」!
最新文章
- Python Logging模块的简单使用
- 三、jQuery--jQuery基础--jQuery基础课程--第7章 jQuery 动画特效
- [JBoss] - 在Jboss 7.1 AS中打印hibernate的SQL方法
- Nginx 的线程池与性能剖析
- hibernate 一张数据表的流程
- 敏捷开发之Scrum
- BinarySearchTree-二叉搜索树
- vue初级学习--路由router的编写(resolve的使用)
- PLEC-交流电机系统+笔记
- DCGAN 代码简单解读
- 『集群』007 如何测试Slithice源代码
- 软件可维护性的影响因素&;如何提升
- javap浅析-书籍第3章的手写稿样稿
- ubuntu 安装 wireshark
- vue计算属性和侦听器
- 使用jQuery+huandlebars遍历if判断不足引用helper
- [Linux] 设置系统时区
- Ubuntu配置静态IP
- 从零开始学JAVA(09)-使用SpringMVC4 + Mybatis + MySql 例子(注解方式开发)
- vs2013的安装及测试(第三周)