首页 > 试题广场 >

按之字形顺序打印二叉树

[编程题]按之字形顺序打印二叉树
  • 热度指数：537982 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：,树上每个节点的val满足
要求：空间复杂度：，时间复杂度：
例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1

输入

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

输出

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

说明

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。
示例2

输入

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

输出

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

输入

{1,2,3,4,5}

输出

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

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python
不愿吃饼的三文鱼很调皮头像 不愿吃饼的三文鱼很调皮 
class Solution:
    # 思路：层序遍历，用队列
    def Print(self, pRoot):
        if not pRoot:
            return None
        queue = [pRoot]
        res = []
        i=0
        while queue:
            num = len(queue)
            temp = []
            while num > 0:
                cur = queue.pop(0)
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
                num -= 1
            if i % 2 == 0:
                res.append(temp)
            else:
                res.append(temp[::-1])
            i += 1
        return res

发表于 2021-07-17 12:09:34 回复(0)
Python
吾三省啊头像 吾三省啊
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = [pRoot]
        result = []
        level = 1
        while res:
            length = len(res)
            res_temp = []
            for i in range(length):
                temp = res.pop(0)
                res_temp.append(temp.val)
                if temp.left:
                    res.append(temp.left)
                if temp.right:
                    res.append(temp.right)
            if level %2==0:
                result.append(res_temp[::-1])
            else:
                result.append(res_temp)
            level +=1
        return result
发表于 2021-05-10 16:25:40 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res=[]
        level=0
        list1=[pRoot]
        while list1:
            tmp=list1
            val=[]
            list1=[]
            for item in tmp:
                val.append(item.val)
                if item.left:
                    list1.append(item.left)
                if item.right:
                    list1.append(item.right)
            if level%2==0:
                res.append(val)
            else:
                res.append(val[::-1])
            level+=1
        return res

发表于 2021-04-18 22:21:22 回复(0)
Python
Hiroi头像 Hiroi
Python 和每一行打印是一样的，用队列，只不过加一个判断是奇数行还是偶数行的n，负责反向。 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
            return []
        output = []
        n = 0
        queue = [pRoot]
        while queue:
            temp = []
            for i in range(len(queue)):
                cur = queue.pop(0)
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            if n%2:
                temp = temp[::-1]
            n+=1
            output.append(temp)
        return output


发表于 2021-04-18 21:17:48 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        curRes = []
        curCnt = 1
        nextCnt = 0
        pQueue = [pRoot]
        FLAG = 1
        while pQueue:
            p = pQueue.pop(0)
            if FLAG:
                curRes.append(p.val)
            else:
                curRes.insert(0, p.val)
            curCnt -= 1
            if p.left:
                pQueue.append(p.left)
                nextCnt += 1
            if p.right:
                pQueue.append(p.right)
                nextCnt += 1
            if curCnt == 0:
                FLAG = not FLAG
                res.append(curRes)
                curRes = []
                curCnt = nextCnt
                nextCnt = 0
        return res

发表于 2020-10-19 16:22:51 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    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)
        returnResult = []
        for i,v in enumerate(result):
            if i%2 == 0:
                returnResult.append(result[i])#这里用（v）也可
            else:
                returnResult.append(result[i][::-1])#这里用v[::-1]也可
        return returnResult

发表于 2020-08-06 20:44:05 回复(0)
Python
生下来就会跑头像 生下来就会跑 
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:return [] 
        result = []
        res = [pRoot]
        flag = 0
        while res:
            resnext=[]
            num = []
            for i in res:
                if not i : break
                num.append(i.val)
                if i.left is not None:
                    resnext.append(i.left)
                if i.right is not None:
                    resnext.append(i.right)
            if flag == 0:
                result.append(num[::])
                flag = 1
            else:
                result.append(num[::-1])
                flag = 0
            res = resnext
        return result

发表于 2020-06-20 00:56:51 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    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 islastlayer(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.islastlayer(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
        for i in range(len(All)):
            if i%2==1:
                All[i].reverse()
        return All
        # write code here

发表于 2020-05-30 16:06:35 回复(0)
Python
橘子汽水超人2号头像 橘子汽水超人2号

Python Solution

一行行地把.val拿出来... 
class Solution:
    def Print(self, pRoot):
        i,res,tmpList = 1,[],[pRoot]
        while tmpList and tmpList[0]:
            res.append([x.val for x in tmpList][::i])
            dummy = []
            for y in tmpList:
                y.left and dummy.append(y.left)
                y.right and dummy.append(y.right)
            tmpList=dummy
            i=-i
        return res
中间总是给我报错`int object has no len()`，原来是因为，输出需要二维列表

编辑于 2020-06-05 13:51:55 回复(0)
Python
llfgo4it头像 llfgo4it
写的有些繁琐，大概就是将每一行出来的节点缓存到一个列表中，然后设定一个符号位。每次如果是正序遍历缓存列表，那么就符号位反转，以逆序遍历列表，最后添加结果。 
from collections import deque
class Solution:
    def Print(self, pRoot):
        # write code here
        if pRoot == None:
            return []
        s = deque()
        s.append(pRoot)
        s.append(None)
        res, tmp, bak, flag  =[],[],[], False
        # flag=True, -> ; flag=False, <-
        while len(s)!=1:
            t = s.popleft()
            if t!=None:
                # element go to deque as uasual
                if t.left != None:
                    s.append(t.left)
                if t.right!=None:
                    s.append(t.right)
                bak.append(t)
            else:
                s.append(None)
                if flag:
                    tmp = [bak.pop().val for i in range(len(bak))]
                else:
                    tmp = [i.val for i in bak]
                res.append(tmp)
                tmp,bak  = [], []
                flag = not flag
        if flag:
            tmp = [bak.pop().val for i in range(len(bak))]
        else:
            tmp = [i.val for i in bak]
        res.append(tmp)
        return res


编辑于 2020-03-24 17:26:13 回复(0)
Python
牛客216005109号头像 牛客216005109号
采用层次遍历的思想, 
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        queue,flag,res = [pRoot],True,[]
        while len(queue) > 0:
            size,tmp = len(queue),[]
            while size > 0:
                node = queue.pop(0)
                size -= 1
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if flag:
                res.append(tmp)
                flag = False
            else:
                tmp.reverse()
                res.append(tmp)
                flag = True
        return res


发表于 2020-03-13 20:56:22 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        queue = [pRoot]
        ans = []
        count = 0
        while queue:
            temp = []
            res = []
            count += 1
            for i in queue:
                res.append(i.val)
                if i.left:
                    temp.append(i.left)
                if i.right:
                    temp.append(i.right)
            queue = temp
            if count%2 == 0:
                res = res[::-1]
            ans.append(res)
        return ans

发表于 2020-03-03 18:06:52 回复(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 Print(self, pRoot):
        res = []
        if not pRoot:
            return res
        else:
            stack1 = []
            stack2 = []
            stack1.append(pRoot)
            flag_left_right = True
            while stack1:
                res_level = []
                for i in range(len(stack1)):
                    top = stack1.pop()
                    res_level.append(top.val)
                    if flag_left_right:
                        if top.left: stack2.append(top.left)
                        if top.right: stack2.append(top.right)
                    else:
                        if top.right: stack2.append(top.right)
                        if top.left: stack2.append(top.left)
                res.append(res_level)
                stack1, stack2 = stack2, stack1
                flag_left_right = not flag_left_right
            return res


s = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ans = s.Print(root)
print(ans)
编辑于 2020-02-28 15:29:38 回复(0)
Python
黄沙遮天头像 黄沙遮天 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        currentlist=[pRoot]
        result=[]
        while currentlist:
            #此题为设置多层列表，每一层会将所有root节点处理完，才会处理下一层节点
            nextlist=[]
            res=[]
            for i in currentlist:
                #把每一层的节点加入到res列表，currentlist列表中每个节点在同一层
                res.append(i.val)
                if i.left:
                    nextlist.append(i.left)
                if i.right:
                    nextlist.append(i.right)
            #将下一层的所有节点的列表取代现有的节点列表
            currentlist=nextlist
            #将同一层的所有值作为总列表的一个元素
            result.append(res)
        returnresult=[]
        for i,v in enumerate(result):
            #按照之字型顺序进行打印
            if i%2==0:
                returnresult.append(v)
            else:
                returnresult.append(v[::-1])
        return returnresult
关键点就是设计子列表，且同一层节点位于同一个列表中，遍历整个列表，将其子元素都加入到子列表中，当遍历完后，用子列表取代现有列表，则此时的列表表示的都是同一层的节点。
发表于 2020-02-01 21:02:20 回复(0)
Python
小辣鸭头像 小辣鸭
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
    奇数层和偶数层
    两个栈
    返回一个嵌套列表
    参考
        https://blog.csdn.net/qq_40608516/article/details/91128825

'''

class Solution:
    def Print(self, pRoot):
        # write code here
        root = pRoot
        if root == None:
            return []
        queue = [root]
        stack = []
        count = 1
        res = []
        tmp = []
        while queue or stack:
            #  每次循环弹出最左边的节点并打印节点值
            if count % 2:
                now_node = queue.pop(0)
                tmp.append(now_node.val)
                #  检测到换层
                if not queue:
                    res.append(tmp)
                    tmp = []
                    count = 0
                if now_node.left != None:
                    stack.append(now_node.left)
                if now_node.right != None:
                    stack.append(now_node.right)
            else:
                now_node = stack.pop()
                tmp.append(now_node.val)
                #  检测到换层
                if not stack:
                    res.append(tmp)
                    tmp = []
                    count = 1
                if now_node.right != None:
                    queue.insert(0, now_node.right)
                if now_node.left != None:
                    queue.insert(0, now_node.left)
        return res
发表于 2019-12-23 16:12:09 回复(0)
Python
bywuuu头像 bywuuu
PYTHON暴力法：
思路：只要先进行一次层序遍历，然后对这个存储了所有节点（或者结点的值）的数组进行一下奇数行偶数行的变化就够了，从0行开始，0行不倒序，奇数行不倒序，偶数行倒序 

class Solution:
    def __init__(self):
        self.res = [[]]

    def Print(self, pRoot):
        self.get_level_tree(pRoot,1)
        isTurn = False
        result = []
        self.res.pop()
        for i in range(len(self.res)):
            if isTurn:
                self.res[i]=self.res[i][::-1]
            isTurn =  not isTurn
            
        return self.res

    # write code here

    def get_level_tree(self, my_root, level):
        if not my_root:
            return None
        else:
            self.res[level - 1].append(my_root.val)
            if len(self.res) == level:
                self.res.append([])
            self.get_level_tree(my_root.left, level + 1)
            self.get_level_tree(my_root.right, level + 1)



编辑于 2019-12-15 11:59:48 回复(0)
Python
开水在笑头像 开水在笑 
# Python大法
# 做完后一题后再回过来用递归
class Solution:
    def Print(self, pRoot):
        # write code here
        # 广度优先遍历----队列

        if not pRoot:
            return []
        
        rsl = []
        def align(pRoot, depth):
            if pRoot:
                if len(rsl) < depth:
                    rsl.append([])
                    
                if depth % 2 == 1:
                    rsl[depth - 1].append(pRoot.val)
                else:
                    # 偶数行，倒序打印，用insert一直往前插入
                    rsl[depth - 1].insert(0,pRoot.val)
                # 调用递归
                align(pRoot.left, depth+1)
                align(pRoot.right, depth+1)
        align(pRoot, 1)
        return rsl

编辑于 2019-12-05 13:45:56 回复(0)
Python
卑微求offer的硕狗在读头像 卑微求offer的硕狗在读 
# -*- coding:utf-8 -*-
class Solution:
    def Print(self, pRoot):
        # write code here
        nodelist=[pRoot]
        res=[]
        restemp=[]
        flag=0 #0代表从左向右
        while nodelist:
            temp=[]
            restemp=[]
            for i in range(len(nodelist)-1,-1,-1):
                if nodelist[i]:
                    restemp.append(nodelist[i].val)
                    if flag%2==0:
                        temp.append(nodelist[i].left)
                        temp.append(nodelist[i].right)
                    else:
                        temp.append(nodelist[i].right)
                        temp.append(nodelist[i].left)
            flag=1-flag       
            nodelist=temp
            res.append(restemp)
            
        return res[:-1]

发表于 2019-12-03 16:29:51 回复(0)
提交观点

问题信息

栈 队列 树
难度：
55条回答 116892浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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