首页 > 试题广场 >

从上往下打印二叉树

[编程题]从上往下打印二叉树
  • 热度指数：701870 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000
示例1

输入

{8,6,10,#,#,2,1}

输出

[8,6,10,2,1]
示例2

输入

{5,4,#,3,#,2,#,1}

输出

[5,4,3,2,1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
￣正体不明头像 ￣正体不明
python用队列存储节点太舒服了
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if(root == None):
            return 
        else:
            que.append(root)
        while(len(que) > 0):
            x = que.pop(0)
            res.append(x.val)
            if(x.left != None):
                que.append(x.left)
            if(x.right != None):
                que.append(x.right)
        return res
编辑于 2021-07-02 20:50:32 回复(0)
Python
什么题目都蒙对头像 什么题目都蒙对
class Solution:
    def printFromTopToBottom(self,root):
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            temp = stack
            stack = []
            for node in temp:
                res.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        return res
发表于 2021-06-04 17:15:11 回复(1)
Python
Quinn_5400头像 Quinn_5400
使用队列的特性就可以了

# -*- 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 not root:
            return []
        queue = [root,]
        r = []
        while queue:
            if queue[0].left is not None:
                queue.append(queue[0].left)
            if queue[0].right is not None:
                queue.append(queue[0].right)
            r.append(queue[0].val)
            queue.pop(0)
        return r

发表于 2021-04-26 19:03:42 回复(0)
Python
牛客440958841号头像 牛客440958841号 
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        if not root: return []
        # write code here
        res = []
        queue = [root]
        while queue:
            temp = queue.pop(0)
            res.append(temp.val)
            if temp.left: queue.append(temp.left)
            if temp.right: queue.append(temp.right)
        return res

发表于 2021-03-17 09:22:54 回复(0)
Python
渔舟唱晚2022头像 渔舟唱晚2022
层次遍历，定义队列，存储未访问的结点。 
def PrintFromTopToBottom(self, root):
    # write code here
    nodeList = []
    nodeQueue= []
    while root or len(nodeQueue) != 0:
        if root:
            nodeList.append(root.val)
            nodeQueue.append(root.left)
            nodeQueue.append(root.right)
        root = nodeQueue.pop(0)
    return nodeList


编辑于 2020-11-10 15:01:09 回复(0)
Python
SapphireZ头像 SapphireZ 
class Solution:
    def PrintFromTopToBottom(self, root):
        layer_list = [root]
        if root is None:
            return []
        for node in layer_list: # 遍历每一层，元素加到列表末尾
            if node.left:
                layer_list.append(node.left)
            if node.right:
                layer_list.append(node.right)
        return [i.val for i in layer_list]
有比我这更简单的吗？哈哈哈，使了点小聪明，动态改变循环的列表，也达到了队列的效果
发表于 2020-09-25 00:35:42 回复(0)
Python
www_helloworld_cn头像 www_helloworld_cn

BFS遍历二叉树，每次都从左到右遍历两个子节点

# -*- 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
        # BFS 遍历二叉树，正好可以满足深度逐渐加1
        if root == None:
            return []
        que = [root]
        '''val = [root.val]
        while len(que) != 0:
            branch_root = que[0]
            del(que[0])
            if branch_root.left != None:
                que.append(branch_root.left)
                val.append(branch_root.left.val)
            if branch_root.right!= None:
                que.append(branch_root.right)
                val.append(branch_root.right.val)
        '''
        val = []
        while len(que) != 0:
            branch_root = que[0]
            val.append(branch_root.val)
            del(que[0])
            if branch_root.left != None:
                que.append(branch_root.left)
            if branch_root.right!= None:
                que.append(branch_root.right)

        return val
发表于 2020-08-04 09:44:06 回复(0)
Python
DDooo头像 DDooo 
# -*- 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
        res = []
        if not root:
            return []
        currentStack = [root]#将root节点放到栈中，以开始进行遍历
        while currentStack:
            nextStack = [] 
            for i in currentStack:
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
                res.append(i.val)
            currentStack = nextStack
        return res

发表于 2020-07-30 15:43:04 回复(0)
Python
sk8_wt头像 sk8_wt 
class Solution:
    def PrintFromTopToBottom(self, root):
        if not root:
            return []
        self.list_print = []
        self.dayin([root])
        return self.list_print
        
    def dayin(self,root_list):
        if not root_list:
            return 
        list_one_layer = []
        for root in root_list:
            self.list_print.append(root.val)
            if root.left:
                list_one_layer.append(root.left)
            if root.right:
                list_one_layer.append(root.right)
        self.dayin(list_one_layer)
        return

编辑于 2020-07-08 22:21:34 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- 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):
        if root ==None:
            return []
        if root.left==None and root.right==None:
            return [root.val]
        q=[]
        q.append(root)
        re=[]
        while len(q)!=0:
            re.append(q[0].val)
            if q[0].left!=None:
                q.append(q[0].left)
            if q[0].right!=None:
                q.append(q[0].right)
            q.pop(0)
        return re
            
        # write code here

发表于 2020-05-29 21:45:01 回复(0)
Python
accer头像 accer 
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        (1387)# write code here
        array = []
        if root == None:
            return array
        nodeList = [root]
        while len(nodeList):
            node = nodeList.pop(0)
            array.append(node.val)
            if node.left != None:
                nodeList.append(node.left)
            if node.right != None:
                nodeList.append(node.right)
        return array

发表于 2020-03-04 21:57:45 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def PrintFromTopToBottom(self, root):
        if not root:
            return []
        else:
            ans = []
            queue = [root]
            while queue:
                cur_node = queue.pop(0)
                ans += [cur_node.val]
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
        return ans

发表于 2020-03-02 11:20:39 回复(0)
Python
牛客447097232号头像 牛客447097232号 
# -*- coding:utf-8 -*-
"""
使用一个队列
广度搜索，探测到一个节点的时候，把它的左右子节点加入到队尾
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def PrintFromTopToBottom(self, root):
        res = []
        if not root:
            return res
        else:
            q = []
            q.append(root)
            while q:
                first = q.pop(0)
                res.append(first.val)
                if first.left:
                    q.append(first.left)
                if first.right:
                    q.append(first.right)
            return res


s = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ans = s.PrintFromTopToBottom(root)
print(ans)
发表于 2020-02-28 14:46:58 回复(0)
Python
牛客108916715号头像 牛客108916715号
通过递归实现
每一层都往一个空stack里放从左往右的节点
把每一层的连接起来
最后记得加上根节点 
class Solution:
    def __init__(self):
        self.res=[]
    def PrintFromTopToBottom(self, root):
        if not root: return []
        stack=[]
        if root.left:
            stack.append(root.left.val)
        if root.right:
            stack.append(root.right.val)
        self.res+=stack
        self.PrintFromTopToBottom(root.left)
        self.PrintFromTopToBottom(root.right)
        return [root.val]+self.res


发表于 2020-01-12 19:45:28 回复(0)
Python
lih627头像 lih627

Python

# -*- 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 not root:
            return []
        res = [root]
        for tmp in res:
            if tmp.left:
                res.append(tmp.left)
            if tmp.right:
                res.append(tmp.right)
        return [i.val for i in res]
发表于 2019-12-19 00:58:01 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        l=[]
        list1=[]
        if root==None:
            return list1
        l.append(root)
        p=l.pop(0)
        while(p!=None):
             if p!=None:
                list1.append(p.val)
             #此题的关键处就在于判断左右子树是否为空，只有在非空时才把节点加入进去
             if p.left!=None:
                l.append(p.left)
             if p.right!=None:   
                l.append(p.right)
             #只有当列表非空时才能继续循环弹出，否则只能跳出循环
             if len(l)!=0:
                p=l.pop(0)
             else:
                break
        return list1
我把一切都写在了代码里，快去寻找吧
发表于 2019-12-10 22:34:00 回复(0)
Python
天山剑客头像 天山剑客 
# -*- 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
        res = list()
        queue = list()
        tmp = list()
        
        if root is not None:
                queue.append(root)
                while queue:
                        node = queue.pop(0)
                        res.append(node.val)
                        if node.left is not None:
                                tmp.append(node.left)
                        if node.right is not None:
                                tmp.append(node.right)
                        
                        if not queue:
                                queue = tmp
                                tmp = []
                return res
        else:
                return []
        

发表于 2019-12-01 13:52:47 回复(0)
Python
Kirto先森头像 Kirto先森 
# -*- 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):
        #层次遍历
        #递归
        level = []
        def loop(root, depth):
            if not root:
                return []
            #遇到新层就让res新增一个列表
            if len(level)==depth:
                level.append([])
            level[depth].append(root.val)
            loop(root.left, depth+1)
            loop(root.right, depth+1)
        loop(root, 0)
        if not level:
            return []
        #此时的level是一个二维列表
        from functools import reduce
        return reduce(lambda x,y: x+y, level)
        '''
        #迭代方式2
        if not root:
            return []
        res = []
        cur_level = [root]
        while cur_level:
            next_level = []
            for node in cur_level:
                res.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            cur_level = next_level
        return res
        
        #迭代方式1
        if not root:
            return []
        res = []
        from collections import deque
        queue = deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return res
        '''

发表于 2019-11-08 16:48:32 回复(0)
提交观点

问题信息

队列 树
难度：
76条回答 133263浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号