《剑指offer》面试题16：从上往下打印二叉树（Python）

2021-03-31 06:27

阅读：343

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路：

这个题目其实非常基础了，也就是直接使用BFS广度优先搜索算法对整棵二叉树进行遍历即可，我们最后返回的是一个数组 "[]",把遍历之后的元素放到这个数组当中即可。为了进行BFS，我们首先新建一个队列，将树根部的节点放到队列里，然后弹出，弹出的同时将刚刚弹出的Node下面的两个节点放到队列的后面，这样在循环当中又可以遍历后面的Node了。同时这个题比较特殊，我们返回的是一个列表，因此即使给定的root里面啥也没有，我们返回的则是空列表而不是None。代码如下所示：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if root == None:
            return []
        ret = []
        queue = []
        queue.append(root)
        while queue:
            now_node = queue.pop(0)
            ret.append(now_node.val)
            if now_node.left != None:
                queue.append(now_node.left)
            if now_node.right != None:
                queue.append(now_node.right)
        return (ret)

上一篇：美团叶子算法

下一篇：python request 中文乱码问题

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《剑指offer》面试题16：从上往下打印二叉树（Python）
文章链接：http://soscw.com/index.php/essay/70341.html

亲，登录后才可以留言！

《剑指offer》面试题16：从上往下打印二叉树（Python）

解题思路：

评论

热门文章

推荐文章

最新文章

置顶文章