【题目】
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.
【代码】
/*********************************
* 日期：2014-10-16
* 作者：SJF0115
* 题号: Binary Tree Level Order Traversal II
* 来源：https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <malloc.h>
#include <vector>
#include <queue>
using namespace std;
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> > vec;
vector<int> v;
if(root == NULL){
return vec;
}
queue<TreeNode*> q;
q.push(root);
//当前层的个数
int count = 1;
//下一层的个数
int nextCount = 0;
while(!q.empty()){
//取队列头元素
TreeNode* p = q.front();
//存储元素
v.push_back(p->val);
q.pop();
count--;
//左右子节点
if(p->left){
q.push(p->left);
nextCount++;
}
if(p->right){
q.push(p->right);
nextCount++;
}
//一层访问完毕
if(count == 0){
count = nextCount;
nextCount = 0;
vec.insert(vec.begin(),v);
v.clear();
}
}
return vec;
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
char data;
//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data-'0';
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
vector<vector<int> > v = solution.levelOrderBottom(root);
for(int i = 0;i < v.size();i++){
for(int j = 0;j < v[i].size();j++){
cout<<v[i][j];
}
cout<<endl;
}
}
//13#5##49###
