剑指Offer - 面试题32 - III. 从上到下打印二叉树 III（BFS，queue+stack）
剑指Offer - 面试题32 - III. 从上到下打印二叉树 III（BFS，queue+stack）
Michael阿明
发布于 2020-07-13 17:35:34
发布于 2020-07-13 17:35:34
1. 题目
请实现一个函数按照之字形顺序打印二叉树， 即第一行按照从左到右的顺序打印， 第二层按照从右到左的顺序打印， 第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 用队列实现遍历
- 设置
bool变量实现每行的左右插入顺序 stack对一行节点进行反转
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return {};
queue<TreeNode*> q;
TreeNode *tp;
q.push(root);
stack<TreeNode*> s;
int size;
vector<int> lv;
vector<vector<int>> ans;
bool flag = false;
while(!q.empty())
{
size = q.size();
flag = !flag;//每行反转一下
while(size--)
{
tp = q.front();
q.pop();
lv.push_back(tp->val);
if(flag)//偶数行
{ //先左后右
if(tp->left) s.push(tp->left);
if(tp->right) s.push(tp->right);
}
else//奇数行
{ //先右后左
if(tp->right) s.push(tp->right);
if(tp->left) s.push(tp->left);
}
}
while(!s.empty())
{ //反转加入队列
q.push(s.top());
s.pop();
}
ans.push_back(lv);
lv.clear();
}
return ans;
}
};
在这里插入图片描述
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录