题目:solveNQueenss
要求:
给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
样例:
给一棵二叉树
{3,9,20,
#,
#,15,7
} ：
3
/
\
9 20
/
\
15 7
返回他的分层遍历结果：
[
[3
],
[9,20
],
[15,7
]
]
算法要求:
挑战1：只使用一个队列去实现它 挑战2：用DFS算法来做
解题思路:
用i来记录当前层遍历了几个，n来记录当前层有几个，j来记录一共遍历了几个有效结点，size表示结点数。 用DFS的话，二个参数一个是当前结点，一个是当前层数。
算法如下:
int getSize(TreeNode *root) {
if (root == NULL) {
return 1;
}
return getSize(root->left) + getSize(root->right);
}
vector<vector<int> > levelOrder(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;
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;
if (!v->empty()) {
vec.push_back(*v);
v =
new vector<int>();
}
}
if (now) {
que.push(now->left);
que.push(now->right);
}
else{
que.push(NULL);
que.push(NULL);
}
}
if (!v->empty()) {
vec.push_back(*v);
}
return vec;
}
