原题链接:http://oj.leetcode.com/problems/binary-tree-level-order-traversal/这道题要求实现树的层序遍历,其实本质就是把树看成一个有向图,然后进行一次广度优先搜索,这个图遍历算法是非常常见的,这里同样是维护一个队列,只是对于每个结点我们知道它的邻接点只有可能是左孩子和右孩子,具体就不仔细介绍了。算法的复杂度是就结点的数量,O(n),空间复杂度是一层的结点数,也是O(n)。代码如下:public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root == null)
return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int curNum = 0;
int lastNum = 1;
ArrayList<Integer> list = new ArrayList<Integer>();
while(!queue.isEmpty())
{
TreeNode cur = queue.poll();
lastNum--;
list.add(cur.val);
if(cur.left!=null)
{
queue.add(cur.left);
curNum ++;
}
if(cur.right!=null)
{
queue.add(cur.right);
curNum++;
}
if(lastNum==0)
{
lastNum = curNum;
curNum = 0;
res.add(list);
list = new ArrayList<Integer>();
}
}
return res;
}
层序遍历也是树的一种遍历方式,在某些题目中会比较实用,不过这样其实更接近于图的问题了,在有些树的题目中层序遍历提供了更好的方法,所以还是得熟悉哈。层序遍历也是树的一种遍历方式,在某些题目中会比较实用,不过这样其实更接近于图的问题了,在有些树的题目中层序遍历提供了更好的方法,所以还是得熟悉哈。这道题还有一个变体Binary
Tree Zigzag Level Order Traversal,其实也是进行广度优先搜索,不过因为要求不同,要换一种数据结构来记录层节点,有兴趣可以看看。
分享到:
相关推荐
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
[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...
102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造...
102-Binary Tree Level Order Traversal199-Binary Tree Right Side View:层次遍历的一个运用树的构造给出前中后序的序列中的两个,构造一棵树。递归。前序 parent left-child right-child中序 left-child parent ...
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 ...
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和...
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 打卡...
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
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 ...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...binary_tree_inorder_traversal ...binary_tree_level_order_traversal_I
leetcode下载 我会尽力将LeetCode上所有的题目都用动画的形式演示出来,计划用3到4年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 五分钟学算法 ,您可以关注获取最新的文章。 Problems ID Problem...
leetcode中文版 我会尽力将LeetCode上所有的题目都用动画的形式演示出来,计划用3到4年时间去完成它,期待与你见证这一天! 文章最新首发于微信公众号 五分钟学算法 ,您可以关注获取最新的文章。 Problems ID ...
leetcode 树节点力码 Leetcode 链接: 包含已解决的 Leetcode 问题的存储库。 问题根据难度编号和放置,然后根据用于解决问题的语言。 它们各自的编号放在标题之前。 问题的一般描述包含在文件本身的随附注释中。 ...
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. ...
leetcode中文版车鸟 一组用python编写的算法。 种类 冒泡排序 插入排序 归并排序 桶排序 计数排序 基数排序 ...balance_binary_tree ...binary_tree_inorder_traversal ...binary_tree_level_order_traversal_I