Title:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
] 思路：使用队列，并且每次记录下每层的数目，这样从队列中取元素也就清楚了每层的元素
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> Q;
vector<vector<int> > results;
if (!root)
return results;
vector<int> result;
Q.push(root);
int count_pre = ;
int count_cur = ;
while (!Q.empty()){
TreeNode* top = Q.front();
result.push_back(top->val);
Q.pop();
count_pre--;
if (top->left){
Q.push(top->left);
count_cur++;
}
if (top->right){
Q.push(top->right);
count_cur++;
}
if (count_pre == ){
count_pre = count_cur;
count_cur = ;
results.push_back(result);
result.clear();
}
}
return results;
}
};
还可以使用递归。关键是要保存到对应的层数
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > result;
travel(root,result,);
return result;
}
void travel(TreeNode* root,vector<vector<int> > &result,int level){
if (!root)
return ;
if (level > result.size())
result.push_back(vector<int> ());
result[level-].push_back(root->val);
travel(root->left,result,level+);
travel(root->right,result,level+);
}
};
Title:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
一样的思路啊！如果不使用递归，则使用一个标记，看这层是否反转，直接使用reverse函数即可。如果使用递归，则也是在相应的层反转。但是因为是在插入的过程中，所以应该是插入每层的vector头。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > results;
if (!root)
return results;
queue<TreeNode*> Q;
Q.push(root);
int count_pre = ;
int count_cur = ;
vector<int> result;
bool flag = false;
while (!Q.empty()){
TreeNode* node = Q.front();
Q.pop();
result.push_back(node->val);
count_pre--;
if (node->left){
Q.push(node->left);
count_cur++;
}
if (node->right){
Q.push(node->right);
count_cur++;
}
if (count_pre == ){
count_pre = count_cur;
count_cur = ;
if (flag){
reverse(result.begin(),result.end());
results.push_back(result);
}else{
results.push_back(result);
}
result.clear();
flag = !flag;
}
}
return results;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > results;
travel(root,,results,true);
return results;
}
void travel(TreeNode* root, int level, vector<vector<int> > &results, bool left_to_right){
if (!root)
return;
if (level > results.size())
results.push_back(vector<int>());
if (left_to_right)
results[level-].push_back(root->val);
else
results[level-].insert(results[level-].begin(),root->val);
travel(root->left,level+,results,!left_to_right);
travel(root->right,level+,results,!left_to_right);
}
};