题目:solveNQueens
要求:
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
样例:
给出一棵二叉树
{3,9,20,
#,
#,15,7
},
3
/
\
9 20
/
\
15 7
返回其锯齿形的层次遍历为：
[
[3
],
[20,9
],
[15,7
]
]
算法要求:
无
解题思路:
在每层判断下是不是该转置。
算法如下:
int getSize(TreeNode *root) {
if (root == NULL) {
return 1;
}
return getSize(root->left) + getSize(root->right);
}
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> > vec;
if (root == NULL) {
return vec;
}
int size = getSize(root) -
1;
queue<TreeNode*> que;
que.push(root);
vector<int> *v =
new vector<int>();
int n =
1;
int i =
0;
int j =
0;
bool flag =
true;
while (!que.empty() && j < size) {
TreeNode *now = que.front();
que.pop();
i++;
if (now) {
v->push_back(now->val);
j++;
}
if (i >= n) {
i =
0;
n *=
2;
vector<int> tempVec;
if (!flag) {
vector<int> tempVec2 = *v;
int size2 = v->size();
for (
int i = size2 -
1; i >=
0 ; i--) {
tempVec.push_back(tempVec2[i]);
}
}
flag = !flag;
if (tempVec.empty()) {
tempVec = *v;
}
if (!v->empty()) {
vec.push_back(tempVec);
v =
new vector<int>();
}
}
if (now) {
que.push(now->left);
que.push(now->right);
}
else{
que.push(NULL);
que.push(NULL);
}
}
if (!v->empty()) {
vector<int> tempVec;
if (!flag) {
vector<int> tempVec2 = *v;
int size2 = v->size();
for (
int i = size2 -
1; i >=
0 ; i--) {
tempVec.push_back(tempVec2[i]);
}
}
if (tempVec.empty()) {
tempVec = *v;
}
if (!v->empty()) {
vec.push_back(tempVec);
v =
new vector<int>();
}
}
return vec;
}
};
