剑指offer 32-III 之字形打印二叉树
自己想了两个思路:
1.依然使用层次遍历,只不过在取出每一层的vector后,用库函数reverse每隔一层进行一次翻转,再将其
导入res数组中;
2.利用双端队列 + 层次遍历
思路一代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root)return res;
queue<TreeNode*> q;
q.push(root);
int flag = -1;
while(!empty(q)){
vector<int> arr;
int len = q.size();
for(int i = 0; i < len; i ++ ){
TreeNode* temp = q.front();
q.pop();
arr.push_back(temp->val);
if(temp->left)q.push(temp->left);
if(temp->right)q.push(temp->right);
}
if(flag > 0)
reverse(arr.begin(), arr.end());
flag *= -1;
res.push_back(arr);
}
return res;
}
};
思路二代码
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
deque<TreeNode*> dq;
vector<vector<int>> res;
if(!root)return res;
dq.push_back(root);
int flag = -1;
while(!dq.empty()){
vector<int> arr;
int len = dq.size();
if(flag < 0){
for(int i = 0; i < len; i ++ ){
TreeNode* temp = dq.front();
dq.pop_front();
arr.push_back(temp->val);
if(temp->left)dq.push_back(temp->left);
if(temp->right)dq.push_back(temp->right);
}
}
else{
for(int i = 0; i < len; i ++ ){
TreeNode* temp = dq.back();
dq.pop_back();
arr.push_back(temp->val);
if(temp->right)dq.push_front(temp->right);
if(temp->left)dq.push_front(temp->left);
}
}
res.push_back(arr);
flag *= -1;
}
return res;
}
};