Question :
Given a binary tree, return thelevel ordertraversal 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.
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> > levelOrder(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);
}
return ret;
}
};
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> > levelOrder(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);
}
}
}
};
分享到:
相关推荐
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
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卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add ...Level Order Traversal II], Tree/BFS 2017.06.20 打卡[LeetCode 324. Wiggle Sort II], S
leetcode what_the_dead_men_say 所以这只是一个 repo,我从leetcode.com存储我的问题解决方案。 二叉树 0098 Validate Binary Search Tree - Java Recursive - Java Iterative - Java Inorder 0099 Recover ...
Binary Tree Zigzag Level Order Traversal Recover Binary Search Tree Same Tree Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II ...
Traversal II 144 二叉树的前序遍历 145 二叉树的后序遍历 150 逆波兰表达式求值 167 两数之和 II - 输入有序数组 199 二叉树的右视图 每天一算:Binary Tree Right Side View 203 移除链表元素 206 反转
leetcode下载 ...Traversal II 136 只出现一次的数字 2019-01-16 144 二叉树的前序遍历 145 二叉树的后序遍历 146 LRU缓存机制 LRU缓存机制 2019-01-25 Made by Jun chen 150 逆波兰表达式求值 167 两数之
[102_binary-tree-level-order-traversal.cpp] [103_binary-tree-zigzag-level-order-traversal.cpp] [104_maximum-depth-of-binary-tree.cpp] [105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...binary_tree_inorder_traversal ...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 ...binary_tree_inorder_traversal ...binary_tree_level_order_traversal_I
leetcode 树节点力码 ...binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). Runtime: 8 ms, faster than 100.00% of C++ online submi
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. ...