# [leetcode] Binary Tree Level Order Traversal II

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.

```//Keywords: queue, terminal pointer(mark the end of each level)
//Functions: queue.push(), queue.pop(), queue.front()
//
/**
* 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>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> re;
vector<int> thisRe;
queue<TreeNode*> q;
if(root == NULL){
return re;
}
q.push(root);
TreeNode * levelEndNode = root;
while(!q.empty()){
TreeNode * p = q.front();
q.pop();
if(p->left){
q.push(p->left);
}
if(p->right){
q.push(p->right);
}
thisRe.push_back(p->val);
if(p == levelEndNode){
//new level
levelEndNode = q.back();
re.insert(re.begin(), thisRe);
thisRe.clear();
}
}
return re;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.