binary-tree-level-order-traversal I、II——输出二叉树的数字序列
I
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree{3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
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
\
5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".
/**
* 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> > levelOrder(TreeNode *root) {
vector<vector<int>> res;
if(root==NULL) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int> v;
for(int i=;i<n;i++){
TreeNode *cur=q.front();
q.pop();
v.push_back(cur->val);
if(cur->left!=NULL)
q.push(cur->left);
if(cur->right!=NULL)
q.push(cur->right);
}
res.push_back(v);
}
return res;
}
};
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.
先将结果v存入stack中,最后在从stack倒入res形成倒序,未找到其他好的方法
/**
* 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>> res;
if(root==NULL) return res;
stack<vector<int>> s;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n=q.size();
vector<int> v;
for(int i=;i<n;i++){
TreeNode *cur=q.front();
q.pop();
v.push_back(cur->val);
if(cur->left!=NULL)
q.push(cur->left);
if(cur->right!=NULL)
q.push(cur->right); }
s.push(v);
}
while(!s.empty()){
res.push_back(s.top());
s.pop();
}
return res;
}
};
最新文章
- d3.js读书笔记-1
- iOS开发常见BUG和一些小技巧(ps:耐心看完,很实用)
- 【译】采用MVC模式创建一个简单的javascript App
- cdh集群数据恢复
- 递归函数 Python
- 【Android源代码下载】收集整理android界面UI效果源码
- 【转】 CATransform3D 矩阵变换之立方体旋转实现细节
- POJ 1860 Currency Exchange (SPFA松弛)
- 【Hadoop代码笔记】通过JobClient对Jobtracker的调用详细了解Hadoop RPC
- java与.net比较学习系列(1) 开发环境和常用调试技巧
- rownum(转载)
- Java线程sleep,yield,join,wait方法详解
- javaScript -- touch事件详解(touchstart、touchmove和touchend)
- tcpdump我的交叉编译(mips)
- Redis的基本知识
- HTML - label (转)
- linux学习笔记-wget相关知识
- Kotlin入门(13)类成员的众生相
- 手把手教你写makefile【原创】
- visual studio Lua 调试
热门文章
- 正则表达式 去除所有非ASCII字符
- 轻量级的C++插件框架 - X3 C++ PluginFramework
- PHP魔术函数、魔术常量、预定义常量
- 【bzoj1965】 [Ahoi2005]SHUFFLE 洗牌 欧拉定理
- 【bzoj】P4407于神之怒加强版(莫比乌斯反演)
- 扩展kmp--模板解析
- kb-01-a<;简单搜索--dfs八皇后问题变种>;
- 我要好offer之 C++大总结
- Python [拷贝copy / 深度拷贝deepcopy] | 可视化理解
- mybatis如何传入一个list参数