首页 > 试题广场 >

把二叉树打印成多行

[编程题]把二叉树打印成多行
  • 热度指数：352353 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树多行打印层序遍历的结果是
[
[1],
[2,3],
[4,5]
]

数据范围：二叉树的节点数 ，
要求：空间复杂度 ，时间复杂度

输入描述:
给定一个二叉树的根节点

示例1

输入

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

输出

[[1],[2,3],[4,5]]
示例2

输入

{8,6,10,5,7,9,11}

输出

[[8],[6,10],[5,7,9,11]]
示例3

输入

{1,2,3,4,5}

输出

[[1],[2,3],[4,5]]
示例4

输入

{}

输出

[]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        out=[]
        out.append([pRoot.val])
        layer1=self.Print(pRoot.left)
        layer2=self.Print(pRoot.right)
        n=min(len(layer1),len(layer2))
        for i in range(n):
            layer1[i]=layer1[i]+layer2[i]
        if len(layer1)<len(layer2):
            layer1+=layer2[n:]
        for item in layer1:
            out.append(item)
        return out


发表于 2021-05-11 00:52:30 回复(0)
Python
在下小6头像 在下小6

python解法：
解法1:层次遍历；

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        if not pRoot:
            return []
        q,res = [],[]
        q.append(pRoot)
        while q:
            tmp = []
            for i in range(len(q)):
                p = q.pop(0)
                tmp.append(p.val)
                if p.left is not None:
                    q.append(p.left)
                if p.right is not None:
                    q.append(p.right)
            res.append(tmp)
        return res
发表于 2021-02-21 16:01:44 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        resCurLevel = []
        cntCurLevel = 1
        cntNextLevel = 0
        pQueue = [pRoot]
        while pQueue:
            p = pQueue.pop(0)
            resCurLevel.append(p.val)
            cntCurLevel -= 1
            if p.left:
                pQueue.append(p.left)
                cntNextLevel += 1
            if p.right:
                pQueue.append(p.right)
                cntNextLevel += 1
            if cntCurLevel == 0:
                res.append(resCurLevel)
                resCurLevel = []
                cntCurLevel = cntNextLevel
                cntNextLevel = 0
        return res

编辑于 2020-10-19 16:06:13 回复(0)
Python
OFFER快点来吧啊吧头像 OFFER快点来吧啊吧 
# 二叉树的广度优先遍历改编，每次添加一层的val到一个[]中，并维护下一次要遍历的层
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot == None:
            return []
            
        
        queue = [pRoot]
        res = []
        while queue:
            nextQueue = []
            vals = []
            for node in queue:
                vals.append(node.val)
                if node.left:
                    nextQueue.append(node.left)
                if node.right:
                    nextQueue.append(node.right)
            queue=nextQueue
            res.append(vals)
                        
        return res  
发表于 2020-08-22 13:07:54 回复(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],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot :
            return []
        result =[]
        nodeStack =[pRoot]
        while nodeStack :
            res = []
            nextStack = []
            for i in nodeStack:
                res.append(i.val)
                if i.left:
                    nextStack.append(i.left)
                if i.right:
                    nextStack.append(i.right)
            nodeStack = nextStack
            result.append(res)
        return result
                
                    
注意：None和[  ]的区别
发表于 2020-07-27 18:57:25 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        queue = [pRoot]    #利用队列来存储二叉树，先进先出
        result = []
        while queue:
            res = []    #临时变量，临时存储每一行的数据，用来以后按条件输出
            queue_tmp = []    #创建临时变量队列，用来临时存储遍历i中的左右孩子节点
            for i in queue:
                res.append(i.val)
                if i.left:
                    queue_tmp.append(i.left)
                if i.right:
                    queue_tmp.append(i.right)
            queue = queue_tmp    #将存储的新的节点，赋值到队列中，用来下一次输出用
            result.append(res)
        return result

发表于 2020-06-12 21:35:00 回复(0)
Python
窗外有千纸鹤头像 窗外有千纸鹤 
class Solution:
    def tranverse(self, depth, root, res):
        if root is None:
            return
        if depth not in res.keys():
            res.setdefault(depth, list())
        res[depth].append(root.val)
        self.tranverse(depth + 1, root.left, res)
        self.tranverse(depth + 1, root.right, res)
    
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        res = dict()
        self.tranverse(1, pRoot, res)
        return [[item for item in res[key]] for key in res.keys()]
创建一个字典，key用来表示当前层数
从左到后，遍历完成之后，对应层数的节点序列即字典中对应key的values
遍历输出为二维list
发表于 2020-06-05 19:03:58 回复(0)
Python
橘子汽水超人2号头像 橘子汽水超人2号

Python Solution 

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        res,tmpList=[],[pRoot]
        while tmpList and tmpList[0]:
            dummy=[]
            res.append([x.val for x in tmpList])
            for x in tmpList:
                x.left and dummy.append(x.left)
                x.right and dummy.append(x.right)
            tmpList = dummy
        return res



发表于 2020-06-05 13:58:33 回复(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],[4,5]]
    def __init__(self):
        self.deepth=0
    def shendu(self,p):
        if p==None:
            return 0
        if p.left==None and p.right==None:
            return 1
        self.deepth=max(self.shendu(p.left),self.shendu(p.right))+1
        return self.deepth
    def isnotlastlayer(self,L):
        for item in L:
            if item.left !=None&nbs***bsp;item.right!=None:
                return True
        return False
        
    def Print(self, pRoot):
        p=pRoot
        if p==None:
            return []
        if p.left==None and p.right==None:
            return [[p.val]]
        All=[]
        All.append([p])
        shendu=self.shendu(p)
        i=0
        #while self.isnotlastlayer(All[-1])==True:
        while i<=shendu-2:
            l1=[]
            for j in range(len(All[i])):
                pp=All[i][j]
                l1.append(pp.left)
                l1.append(pp.right)
            for k in range(len(l1)-1,-1,-1):
                if l1[k]==None:
                    l1.pop(k)
            All.append(l1)
            i=i+1
        for i in range(len(All)):
            for j in range(len(All[i])):
                All[i][j]=All[i][j].val
        return All
            
                
        
        
        # write code here

发表于 2020-05-30 16:08:45 回复(0)
Python
打铁工程师头像 打铁工程师
首先写出层序遍历的骨架部分：

然后再对其填充。
需要注意的是，最后会有一个空列表，所以要将出栈           
发表于 2020-05-10 22:13:11 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
                return []
        else:
                queue = list()
                temp = list()
                res = list()
                
                queue.append(pRoot)
                res.append([pRoot.val])
                while queue:
                        node = queue.pop(0)
                        
                        if node.left is not None:
                                temp.append(node.left)
                        if node.right is not None:
                                temp.append(node.right)
                                
                        if not queue:
                                queue = temp
                                if temp:
                                        res.append(list(map(lambda x: x.val, temp)))
                                temp = []
                return res
                                
                                
                                

发表于 2019-12-02 11:28:19 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
比上一题简单,是完成上一题的第一步,即把每一层的值按层数保存在一个列表里 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        if not pRoot:
            return []
        st=[pRoot]
        res=[]
        while st:
            t=[]
            st2=[]
            for i in st:
                t.append(i.val)
                if i.left:
                    st2.append(i.left)
                if i.right:
                    st2.append(i.right)
            res.append(t)
            st=st2
        return res



发表于 2019-11-18 13:44:42 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        cur_layer=[pRoot]
        result=[]
        while cur_layer:
            res=[]
            nextnode=[]
            for i in cur_layer:
                res.append(i.val)
                if i.left:
                    nextnode.append(i.left)
                if i.right:
                    nextnode.append(i.right)
            cur_layer=nextnode
            result.append(res)
        return result

发表于 2019-10-08 15:47:31 回复(0)
Python
Andy-Liu头像 Andy-Liu
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot: return []
        queue = []
        queue = [pRoot]
        res = []
        while queue:
            temp = []
            for m in queue:
                if m.left:
                    temp.append(m.left)
                if m.right:
                    temp.append(m.right)
            r = []
            for n in queue:
                r += [n.val]
            res.append(r)
            queue = temp
        return res
发表于 2019-09-04 10:48:09 回复(0)
Python
BHRY头像 BHRY
发现没有人发python的，我来发一个Python的解法，总体思路和前一个类似，只是多了两个变量来记录还没打印的节点数和下一层的节点数 
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res=[]
        roots=[pRoot]
        temp=[]
        nextLevel=0
        toBePrinted=1
        while roots:
            node=roots.pop(0)
            temp.append(node.val)
            if node.left:
                roots.append(node.left)
                nextLevel+=1
            if node.right:
                roots.append(node.right)
                nextLevel+=1
            toBePrinted-=1
            if toBePrinted==0:
                res.append(temp)
                temp=[]
                toBePrinted=nextLevel
                nextLevel=0
        return res


发表于 2019-09-01 19:49:17 回复(0)
Python
Dayanghe头像 Dayanghe

这是对二叉树进行按层遍历 

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        stack = [pRoot]
        value = []
        while stack:
            temp = []
            tempstack =[]
            for i in stack:
                temp.append(i.val)
                if i.left:
                    tempstack.append(i.left)
                if i.right:
                    tempstack.append(i.right)
            stack = tempstack
            value.append(temp)
        return value
编辑于 2019-07-09 21:58:40 回复(0)
Python
汤普森30头像 汤普森30 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        root = pRoot
        if root is None:
            return []
        res = []
        queue = []
        queue.append(root)
        while len(queue) != 0:
            size = len(queue)
            temp = []
            for i in range(size):
                head = queue[0]
                temp.append(head.val)
                queue.pop(0)
                if head.left is not None:
                    queue.append(head.left)
                if head.right is not None:
                    queue.append(head.right)
            res.append(temp)
        return res

发表于 2019-07-04 19:38:24 回复(0)
Python
LitterF头像 LitterF 
层次遍历，记录深度
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if(pRoot is None):
            return []
        re = []
        quequ = []
        quequ.append(pRoot)
        quequ_dept = [0]
        while(quequ):
            if(quequ[0].left):
                quequ.append(quequ[0].left)
                quequ_dept.append(quequ_dept[0]+1)
            if(quequ[0].right):
                quequ.append(quequ[0].right)
                quequ_dept.append(quequ_dept[0]+1)
            dept = quequ_dept.pop(0)
            if(len(re)<=dept):
                re.append([])
            re[dept].append(quequ.pop(0).val)
        return re
            
            
发表于 2019-06-27 10:25:19 回复(0)
Python
Krahets头像 Krahets
递归： 
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot: return []
        res = []
        self.line(res, [pRoot])
        return res

    def line(self, res, roots):
        tmp, re = [], []
        for r in roots:
            re.append(r.val)
            if r.left: tmp.append(r.left)
            if r.right: tmp.append(r.right)
        res.append(re)
        if tmp: self.line(res, tmp)
发表于 2019-05-22 17:13:19 回复(0)
Python
poteman头像 poteman 
# bfs解法,数据结构用queue,每次pop(0),append左孩子和右孩子
    def Print(self, pRoot):
        if not pRoot:
            return []

        queue = [pRoot]
        res = []

        while queue:
            cnt = len(queue)
            temp = []
            for i in range(cnt):
                cur = queue.pop(0)
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(temp)
        return res
发表于 2019-05-20 23:12:15 回复(0)
提交观点

问题信息

树 广度优先搜索(BFS)
难度：
41条回答 82797浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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