Question :
Given a binary tree, return thebottom-up level ordertraversal 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.
Anwser 1 :
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> ret;
if(root == NULL) return ret;
vector<int> vec;
queue<TreeNode *> Q;
Q.push(root);
int count = 1;
while(!Q.empty()){
vec.clear();
int nextCount = 0; // cal next row count
for(int i = 0; i < count; i++){ // one row count
TreeNode *tmp = Q.front();
Q.pop();
vec.push_back(tmp->val); // save one row val
if(tmp->left){
Q.push(tmp->left);
nextCount++;
}
if(tmp->right){
Q.push(tmp->right);
nextCount++;
}
}
count = nextCount;
ret.push_back(vec);
}
reverse(ret.begin(), ret.end()); //reverse vector
return ret;
}
};
注意点: 添加了一行
reverse(ret.begin(), ret.end()); // reverse vector
Anwser 2 :
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> ret;
if(root == NULL) return ret;
vector<int> vec;
queue<TreeNode *> Q;
queue<TreeNode *> Q2; // extra space
Q.push(root);
while(!Q.empty()){
TreeNode *tmp = Q.front();
Q.pop();
if(tmp != NULL){
vec.push_back(tmp->val);
if(tmp->left) Q2.push(tmp->left);
if(tmp->right) Q2.push(tmp->right);
}
if(Q.empty()){ // one row end
ret.push_back(vec);
vec.clear();
swap(Q, Q2);
}
}
reverse(ret.begin(), ret.end()); // reverse vector
}
};
注意点: 添加了一行
reverse(ret.begin(), ret.end()); // reverse vector
参考推荐:
Binary Tree Level Order Traversal
分享到:
相关推荐
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
102-Binary Tree Level Order Traversal199-Binary Tree Right Side View:层次遍历的一个运用树的构造给出前中后序的序列中的两个,构造一棵树。递归。前序 parent left-child right-child中序 left-child parent ...
102 Binary Tree Level Order Traversal.js(二叉树级订单Traversal.js) 103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和...
https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level ...
leetcode what_the_dead_men_say 所以这只是一个 repo,我从leetcode.com存储我的问题解决方案。 二叉树 0098 Validate Binary Search Tree - Java Recursive - Java Iterative - Java Inorder 0099 Recover ...
Binary Tree Level Order Traversal II Binary Tree Right Side View Invert Binary Tree Binary Search Tree Iterator Binary Tree Zigzag Level Order Traversal Recover Binary Search Tree Same Tree Symmetric ...
leetcode中文版 我会尽力将LeetCode上所有的题目都用动画的形式演示出来,计划用3到4年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 五分钟学算法 ,您可以关注获取最新的文章。 Problems ID ...
leetcode下载 我会尽力将LeetCode上所有的题目都用动画的形式演示出来,计划用3到4年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 五分钟学算法 ,您可以关注获取最新的文章。 Problems ID Problem...
lru缓存leetcode LeetCode_Note leetcode 个人笔记 问题清单 [1_two_sum.cpp] [10_regular-expression-matching.cpp] [100_same-tree.cpp] ...[107_binary-tree-level-order-traversal-ii.cpp] [108_convert-sorted
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...best_time_to_buy_and_sell_stock_II ...binary_tree_level_order_traversal_I
102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...best_time_to_buy_and_sell_stock_II ...binary_tree_level_order_traversal_I
leetcode 树节点力码 Leetcode 链接: 包含已解决的 Leetcode 问题的存储库。 问题根据难度编号和放置,然后根据用于解决问题的语言。 它们各自的编号放在标题之前。 问题的一般描述包含在文件本身的随附注释中。 ...
2sum leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp ...level_order_traversal.cpp - exponentiation_by_squaring.cpp - Maximum_Depth_B
PYTHONhttps://github.com/meetpatel1311/LeetCode/blob/main/Python/103_Binary_Tree_Zigzag_Level_Order_Traversal.py 力扣问题 数字 标题 解决方案 1. 2. 3. 4. 5. 6. 7. 8. 9. 11. 12. 13. 14. 15. 16. 17. 19. ...