Binary Tree Level Order Traversal
Total Accepted: 79463 Total Submissions: 259292 Difficulty: Easy
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) {
vector<vector<int>> res;
vector<int> one_res; TreeNode* p = root;
TreeNode* first = NULL; queue<TreeNode*> que;
if(p) que.push(p); while(!que.empty()){
p = que.front();
que.pop(); if(first == p){//碰到每层的第一个时就把上一层次的所有结点加入结果集
res.push_back(one_res);
one_res.clear();
first = NULL;
} one_res.push_back(p->val); if(first==NULL && p->left!=NULL){
first = p->left;
}
if(first==NULL && p->right!=NULL){
first = p->right;
} if(p->left){
que.push(p->left);
}
if(p->right){
que.push(p->right);
}
} if(!one_res.empty()){
res.push_back(one_res);
}
return res;
}
};
Next challenges: (M) Binary Tree Zigzag Level Order Traversal (E) Binary Tree Level Order Traversal II (M) Binary Tree Vertical Order Traversal
Binary Tree Level Order Traversal II
Total Accepted: 62827 Total Submissions: 194889 Difficulty: Easy
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
1.正序再反转,8ms
/**
* 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 {
private:
void levelOrderBottom(TreeNode* root,vector<vector<int>>& res,int depth){
if(!root) return;
if(depth==res.size()){
res.push_back({});
}
res[depth].push_back(root->val);
levelOrderBottom(root->left,res,depth+);
levelOrderBottom(root->right,res,depth+);
}
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
levelOrderBottom(root,res,);
reverse(res.begin(),res.end());
return res;
}
};
2.先求高度，无需反转，4ms
/**
* 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 {
private:
int getTreeHeith(TreeNode* root){
if(!root) return ;
return max(getTreeHeith(root->left) ,getTreeHeith(root->right)) + ;
}
void levelOrderBottom(TreeNode* root,vector<vector<int>>& res,int depth){
if(!root) return;
res[depth].push_back(root->val);
levelOrderBottom(root->left,res,depth-);
levelOrderBottom(root->right,res,depth-);
}
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
int dep = getTreeHeith(root);
vector<vector<int>> res(dep,vector<int>());
levelOrderBottom(root,res,dep-);
return res;
}
};