[Leetcode][python]Binary Tree Level Order Traversal
[Leetcode][python]Binary Tree Level Order Traversal
蛮三刀酱
发布于 2019-03-26 17:09:52
发布于 2019-03-26 17:09:52
题目大意
实现树的广度优先遍历，每一层上的数据按照从左到右的顺序排列。
解题思路
参考：链接 将树每一层的节点存在一个列表中，遍历列表中的元素，如果该节点有左右节点的话，就把它们加入一个临时列表，这样当遍历结束时，下一层的节点也按照顺序存储好了，不断循环直到下一层的列表为空。
代码
迭代
BFS
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
tree = []
if not root:
return tree
curr_level = [root]
# print(type(root), type(curr_level)) # (<class 'precompiled.treenode.TreeNode'>, <type 'list'>)
# print(curr_level) # 作为list，却并不能遍历整个树
while curr_level:
level_list = []
next_level = []
for temp in curr_level:
level_list.append(temp.val)
if temp.left:
next_level.append(temp.left)
if temp.right:
next_level.append(temp.right)
tree.append(level_list)
curr_level = next_level
return tree补充：
递归
class Solution(object):
def preorder(self, root, level, res):
if root:
if len(res) < level+1: res.append([])
res[level].append(root.val)
self.preorder(root.left, level+1, res)
self.preorder(root.right, level+1, res)
def levelOrder(self, root):
res=[]
self.preorder(root, 0, res)
return res总结
- 正如代码注释，将root外面加括号使得其变为了list。但在下面的for循环中，依然其是作为一个树结构存储的，是否可以理解为这里的括号仅仅是将他变得可被遍历。
之后我
print(temp)得到了：
<precompiled.treenode.TreeNode object at 0x7fbb9a294b50>
<precompiled.treenode.TreeNode object at 0x7fbb9a294d50>
<precompiled.treenode.TreeNode object at 0x7fbb9a294d90>
<precompiled.treenode.TreeNode object at 0x7fbb9a294dd0>
<precompiled.treenode.TreeNode object at 0x7fbb9a294e10>说明确实里面还是树结构。 应该用这个解释来理解，廖雪峰-迭代，可以再看一遍。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年07月20日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。