剑指offer:77-题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
题目描述
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)
数据范围:15000≤n≤1500,树上每个节点的val满足 |val| <= 100∣val∣<=100
要求:空间复杂度:O(n),时间复杂度:O(n)
例如:
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
题解1:使用队列+双向队列
代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
//题解1:不好理解的代码,未优化
// vector<vector<int>> result;
// if(!pRoot) return result;
// queue<TreeNode*> qu;//使用队列
// qu.push(pRoot);//根节点入栈
// bool oddOreven = true;//设置奇偶层,奇数层为true
// while(!qu.empty()){
// vector<int> de;//存放每行结果的双向队列
// int size = qu.size();//保存队列中元素个数
// //将队列中的元素全部拿出
// for(int i =0;i<size;i++){
// TreeNode * temp = qu.front();
// qu.pop();
// if(!temp) continue;
// //将每个节点的左右节点按照从左到右的顺序入队列
// qu.push(temp->left);
// qu.push(temp->right);
// //将元素插入数组中
// de.push_back(temp->val);
// }
// if(oddOreven == false)//偶数层
// reverse(de.begin(), de.end());
// //取出队列中的元素
// if(!de.empty()){ //如果为空,跳过
// result.push_back(de);
// }
// //下次循环层数变为偶数
// oddOreven = oddOreven == true? false:true;
// }
// return result;
//以下代码更加好理解,优化代码
vector<vector<int>> v;
queue<TreeNode*> q;//层次遍历用的队列
bool b = 0;//b=0作为二叉树奇数层
if(!pRoot) return {};
q.push(pRoot);
while(!q.empty()){
vector<int> arr;
//注意:这里的size在循环体中不能改变,所以这里不能直接使用q.size()
//目的:为了求出每层由多少结点
int size = q.size(); //二叉树每层具有多少个元素
for(int i =0;i<size;i++){
TreeNode * temp = q.front();
q.pop();
//将该层结点的子节点全部入队列
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
//将该层的结点入数组中
arr.push_back(temp->val);
}
//判断是奇数层还是偶数层
if(b){ // 偶数层,则数组反序,然后将之存放如数组v中
reverse(arr.begin(), arr.end());
v.push_back(arr);
b = 0;//偶数层之后必然是奇数层
}else{
v.push_back(arr);
b = 1;//奇数层之后必然是偶数层
}
}
return v;
}
};