Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
69 lines (61 sloc) 1.24 KB
problem:
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],
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
-------------------------------------------------------------------------------------
solution:
////////////////////////////////////////////
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int> > levelOrder(TreeNode *root)
{
vector<vector<int> > ret;
if(root == NULL)
return ret;
queue<TreeNode*> q;
q.push(root);
vector<int> tmp(0);
int count = 1;
int level = 0;
while(!q.empty())
{
tmp.clear();
level = 0;
for(int i = 0; i < count; ++i)
{
root = q.front();
q.pop();
tmp.push_back(root->val);
if(root->left != NULL)
{
q.push(root->left);
level++;
}
if(root->right != NULL)
{
q.push(root->right);
level++;
}
}
ret.push_back(tmp);
count = level;
}
reverse(ret.begin(), ret.end());
return ret;
}