[leetcode] 7. 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 7return 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.OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5The above binary tree is serialized as
"{1,2,3,#,#,4,#,#,5}".
就是按照层数来输出树。思路分为三步，先拿到树的最大层数len，然后再写一个拿指定层的各元素的函数，最后按题目要求写一个返回vector<vector<int>>的函数，里面用一个循环来多次调用之前那个函数，好了，题解如下：
/**
* Definition for binary tree
* 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>> temp;
int len = MaxDepth(root); for (int i = len - 1; i >= 0; i--)
{
vector<int> level;
getElement(level, 0, i, root); temp.push_back(level);
level.clear();
} return temp; } int MaxDepth(TreeNode *temp)
{
if (temp == NULL)
return 0;
else
{
int aspros = MaxDepth(temp->left);
int defteros = MaxDepth(temp->right);
return 1 + (aspros>defteros ? aspros : defteros);
}
} void getElement(vector<int> &level, int count, int len, TreeNode *root)
{
if (root != NULL)
{
if (count == len)
{
level.push_back(root->val);
}
getElement(level, count + 1, len, root->left);
getElement(level, count + 1, len, root->right);
}
}
};
因为题目要求是要从底部向上输出，所以在主函数的for循环里用了倒序。
这次的blog用Live Writer发布，测试一下。
最新文章
- Python之路【第二十四篇】Python算法排序一
- 第三周作业（一）：安装VS以及创建单元测试
- 一道关于阿里简单面试题的反思C/C++
- mysql操作查询结果case when then else end用法举例
- 【Leafletjs】2.添加marker到地图
- puppet学习笔记(二)
- python分页和session和计算时间差
- ORACLE中将数字转换为英文
- Python新手学习基础之循环语句——While循环
- （转）MapReduce 中的两表 join 几种方案简介
- [Django] Base class in the model layer
- ThinkPHP批量添加数据和getField()示例
- css grid布局的首次使用
- 微软云linux服务器FTP文件传输错误解决办法
- [BZOJ]3243 向量内积(Noi2013)
- Mybatis的缓存
- scrapy项目对接Docker
- Java实现单词树(trie)
- 反编译安卓apk以及jar包
- postgresql-分页重复数据探索