请实现一个函数按照之字形顺序打印二叉树, 即第一行按照从左到右的顺序打印, 第二层按照从右到左的顺序打印, 第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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;
}
};