这期内容当中小编将会给大家带来有关怎样实现从上到下打印python二叉树，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
10年品牌的成都网站建设公司,上1000+企业网站设计经验.价格合理,可准确把握网页设计诉求.提供定制网站建设、商城网站建设、小程序定制开发、成都响应式网站建设公司等服务,我们设计的作品屡获殊荣,是您值得信赖的专业的建站公司。
题目描述
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
题目样例
示例
输入
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
输出
[3,9,20,15,7]
题目思考
解决方案
思路
- 经典的 BFS 思路, 将当前节点的左右非空子节点追加到队列结尾, 然后继续往后遍历队列, 最终整个队列就是最后的结果
- 由于这里是树, 所以每个节点只可能被加入队列访问一次, 无需额外的 visit 集合
- 另外这道题不需要分开保存每一层的节点, 所以这里不需要记录当前层的长度之类的情况, 可以直接一次循环搞定
- 数据结构方面, 可以采用列表 + 动态的 for 循环(python 3 适用, 其他语言可能不支持遍历过程中更改容器)或者双端队列 + while 循环(所有语言通用, 每次 pop 最左边的元素作为当前节点)
- 下面的代码是个人觉得比较通用的 BFS 模板, 包括列表和双端队列两种方式的实现, 适用于不需要单独处理每一层节点的情况, 供大家参考
复杂度
代码
方案 1 - 列表 + for 循环
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
# 方案1: 列表+for循环
if not root:
return []
q = [root]
for node in q:
# 只将非空子节点追加到队列
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return [x.val for x in q]
方案 2 - 双端队列 + while 循环
import collections
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
# 方案2: 双端队列+while循环
if not root:
return []
q = collections.deque([root])
res = []
while q:
node = q.popleft()
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
上述就是小编为大家分享的怎样实现从上到下打印python二叉树了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。
网站标题：怎样实现从上到下打印python二叉树
文章地址：
http://cdkjz.cn/article/jcgoci.html
