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],
]
问题描述：给定一个二叉树，从下往上层次遍历所有节点。
可以以层次遍历二叉树，将每层的节点值保存在vector容器中，再将vector容器保存在一个栈中，遍历完成后，将栈中的vector保存到另一个vector中。
class Solution {
public:
vector > levelOrderBottom(TreeNode *root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(root == NULL)
return vector >(0);
queue
> que;
stack > sta;
vector ivec;
TreeNode *pnode = root;
int level = 0;
pair pair_data;
que.push(make_pair(pnode, 1));
while(!que.empty()) {
pair_data = que.front();
que.pop();
pnode = pair_data.first;
level = pair_data.second;
ivec.push_back(pnode->val);
if(que.empty() || level != que.front().second) {
sta.push(ivec);
ivec.clear();
}
if(pnode->left) {
que.push(make_pair(pnode->left, level+1));
}
if(pnode->right) {
que.push(make_pair(pnode->right, level+1));
}
}
vector > vec;
while(!sta.empty()) {
ivec = sta.top();
vec.push_back(ivec);
sta.pop();
}
return vec;
}
};