103. 二叉树的锯齿形层序遍历【BFS】
2021-08-05 本文已影响0人
gykimo
题目:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
我的方法一:广度优先搜索
思路:这个和二叉树的层序遍历是用队列,有一点区别就是奇数层从右往左;所以奇数层往结果vector插入时,从vector头往尾插;偶数层插入时,从vector尾往头插;
方法较简单,代码如下:
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if(!root){
return ret;
}
queue<TreeNode*> q;
q.push(root);
int level_index = 0;
int level_size = 0;
while(!q.empty()){
level_size = q.size();
vector<int> level_result;
level_result.resize(level_size);
if(level_index%2 == 1){
while(level_size > 0){
level_result[level_size-1] = q.front()->val;
level_size--;
if(q.front()->left){
q.push(q.front()->left);
}
if(q.front()->right){
q.push(q.front()->right);
}
q.pop();
}
}else{
for(int i = 0; i<level_size; i++){
level_result[i] = q.front()->val;
if(q.front()->left){
q.push(q.front()->left);
}
if(q.front()->right){
q.push(q.front()->right);
}
q.pop();
}
}
level_index++;
ret.push_back(level_result);
}
return ret;
}
};