leetcode 103. 二叉树的锯齿形层序遍历
程序员文章站
2022-05-21 08:17:54
...
题目:103. 二叉树的锯齿形层序遍历
难度中等
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下:
[
[3],
[20,9],
[15,7]
]
解题思路
通过两个栈,分别存储当前层的数据,还有下一层的数据。
因为从左到右和右到左的入栈方式不同,左右子树的入栈顺序也要跟随改变。
因为栈的性质是先入后出,所以就会将数据颠倒过来,所以就可以达到这个锯齿形层序遍历的效果。
然后出栈输出即可。
代码
//103. 二叉树的锯齿形层序遍历
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
#define LEFT_TO_RIGHT 0 // 从左到右子树入栈
#define RIGHT_TO_LEFT 1 // 从右到左子树入栈
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
stack<TreeNode*> sTree[2]; // 不同奇偶层次,分不同栈
int flag = LEFT_TO_RIGHT;
// 将第1个元素放入
sTree[flag].push(root);
while (1) {
// 第二层开始从右到左入队,下一层就是左到右,来回切换
vector<int> vlevel;
while (sTree[flag].size() > 0)
{
// 取出栈顶元素
TreeNode* node = sTree[flag].top();
sTree[flag].pop();
// 记录要打印的数据
vlevel.push_back(node->val);
// 从右到左子树入栈
if (flag == RIGHT_TO_LEFT) {
if (node->right)
sTree[!flag].push(node->right);
if (node->left)
sTree[!flag].push(node->left);
}
else {// 从左到右子树入栈
if (node->left)
sTree[!flag].push(node->left);
if (node->right)
sTree[!flag].push(node->right);
}
}
// 每层遍历结束,切换一下flag(也就是换栈)
flag = !flag;
// 如果vlevel没有值,说明已经没有子树了跳出循环
if (vlevel.size() == 0)
break;
// 将打印结果放入答案数组中
ans.push_back(vlevel);
}
return ans;
}
};
上一篇: C语言实现(计算球体积)
下一篇: 计算球体积 --JAVA