题目
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)。
数据范围:0≤n≤1500,树上每个节点的val满足∣val∣<=1500
要求:空间复杂度:O(n),时间复杂度:O(n)
例如:
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1
输入:
{1,2,3,#,#,4,5}
返回值:
[[1],[3,2],[4,5]]
说明:
如题面解释,第一层是根节点,从左到右打印结果,第二层从右到左,第三层从左到右。
示例2
输入:
{8,6,10,5,7,9,11}
返回值:
[[8],[10,6],[5,7,9,11]]
示例3
输入:
{1,2,3,4,5}
返回值:
[[1],[3,2],[4,5]]
思路
用两个辅助栈,通过层序遍历二叉树,需要注意的是因为奇数层要从左往右打印,所以前一个偶数层入栈需要先右后左,偶数层正好相反。文章来源:https://www.toymoban.com/news/detail-810399.html
总结规律就是奇数层先左后右入栈,偶数层先右后左入栈。文章来源地址https://www.toymoban.com/news/detail-810399.html
解答代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <stack>
#include <vector>
class Solution {
public:
/**
* @param pRoot TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > Print(TreeNode* pRoot) {
// write code here
vector<vector<int> > res{};
if (pRoot == nullptr) {
return res;
}
stack<TreeNode*> odd_level;// 奇数层,从左往右打印
stack<TreeNode*> even_level;// 偶数层,从右往左打印
int cur = 1;// 当前层索引
odd_level.push(pRoot);
vector<int> tmp;
while (!odd_level.empty() || !even_level.empty()) {
if ((cur&1) == 1) {
// 奇数层
auto size = odd_level.size();
for (int i = 0; i < size; i++) {
auto node = odd_level.top();
tmp.push_back(node->val);
// 先左后右
if (node->left != nullptr) {
even_level.push(node->left);
}
if (node->right != nullptr) {
even_level.push(node->right);
}
odd_level.pop();
}
} else {
// 偶数层
auto size = even_level.size();
for (int i = 0; i < size; i++) {
auto node = even_level.top();
tmp.push_back(node->val);
// 先右后左
if (node->right != nullptr) {
odd_level.push(node->right);
}
if (node->left != nullptr) {
odd_level.push(node->left);
}
even_level.pop();
}
}
++cur;
res.push_back(tmp);
tmp.clear();
}
return res;
}
};
到了这里,关于算法进阶——按之字形顺序打印二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!