* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
private:
vector<TreeNode* > cur_level_nodes_queue;
vector<TreeNode* > next_level_nodes_queue;
void traverse_curlevel(vector<TreeNode* > &cur_level, vector<TreeNode* > &next_level, vector<int> &cur_out) {
int size = cur_level.size();
//cout<<"cur level size:"<<size<<endl;
for ( int i = 0; i < size; i++) {
TreeNode* cur = cur_level[0];
//cout<<"cur value:"<<cur->val<<endl;
if (cur != NULL) {
if (cur->left != NULL) {
next_level.push_back(cur->left);
//cout<<"left value:"<<cur->left->val<<endl;
}
if (cur->right != NULL) {
next_level.push_back(cur->right);
//cout<<"right value:"<<cur->right->val<<endl;
}
cur_out.push_back(cur->val);
}
cur_level.erase(cur_level.begin());
}
}
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
//cout<<"root val:"<<root->val<<endl;
vector<vector<int> > res;
if ( root == NULL) {
return res;
}
cur_level_nodes_queue.push_back(root);
//cout<<"111" << endl;
vector<TreeNode* > *cur_level = &cur_level_nodes_queue;
vector<TreeNode* > *next_level = &next_level_nodes_queue;
//cout<<"2222" << endl;
while (!cur_level->empty()) {
vector<TreeNode* > *tmp = NULL;
vector<int> cur_out;
traverse_curlevel(*cur_level, *next_level, cur_out);
res.push_back(cur_out);
if (next_level->empty()) {
break;
}
tmp = cur_level;
cur_level = next_level;
next_level = tmp;
}
return res;
}
};