当前位置:网站首页>[牛客网刷题 Day5] JZ77 按之字形顺序打印二叉树
[牛客网刷题 Day5] JZ77 按之字形顺序打印二叉树
2022-07-07 08:14:00 【strawberry47】
题目:
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)
思路:
拿到题目的第一想法就是–使用队列呀,奇偶的时候存的东西不一样;行不通。。。
后来又想到使用双边队列,分情况从哪边进哪边出,发现找不到什么规律。。。
看了答案,发现用到了两个栈;也有使用队列,只不过每隔一层就反向打印一下
根据reverse的思路,我花了二十分钟写出来了代码:
class Solution:
def Print(self, pRoot: TreeNode):
# write code here
if pRoot is None:
return None
res = []
q = queue.Queue()
q.put(pRoot)
flag = 0
while not q.empty():
cur_res = []
n = q.qsize()
for i in range(n):
node = q.get()
cur_res.append(node.val)
if node.left:
q.put(node.left)
if node.right:
q.put(node.right)
if flag % 2 != 0:
cur_res.reverse()
res.append(cur_res)
flag = flag+1
return res
答案:
双栈(没咋看明白):
import copy
class Solution:
def Print(self , pRoot: TreeNode) -> List[List[int]]:
head = pRoot
res = []
if not head:
# 如果是空,则直接返回空list
return res
s1, s2 = [], []
# 放入第一次
s1.append(head)
while s1 or s2:
temp = []
# 遍历奇数层
while s1:
node = s1[-1]
# 记录奇数层
temp.append(node.val)
# 奇数层的子节点加入偶数层
if node.left:
s2.append(node.left)
if node.right:
s2.append(node.right)
s1.pop()
# 数组不为空才添加
if len(temp):
res.append(copy.deepcopy(temp))
# 清空本层数据
temp.clear()
# 遍历偶数层
while s2:
node = s2[-1]
# 记录偶数层
temp.append(node.val)
# 偶数层的子节点加入奇数层
if node.right:
s1.append(node.right)
if node.left:
s1.append(node.left)
s2.pop()
if len(temp):
res.append(temp)
return res
边栏推荐
- Video based full link Intelligent Cloud? This article explains in detail what Alibaba cloud video cloud "intelligent media production" is
- Guide de signature du Code Appx
- Pdf document signature Guide
- mysql插入数据创建触发器填充uuid字段值
- 反射效率为什么低?
- 大整数类实现阶乘
- 1321:【例6.3】删数问题(Noip1994)
- Slurm资源管理与作业调度系统安装配置
- STM32产品介绍
- Deconvolution popular detailed analysis and nn Convtranspose2d important parameter interpretation
猜你喜欢
Postman interface test VI
mysql插入数据创建触发器填充uuid字段值
ORM model -- creation and query of data records
1323:【例6.5】活动选择
Postman interface test III
基于gis三维可视化技术的智慧城市建设
[sword finger offer] 42 Stack push in and pop-up sequence
[learning notes - Li Hongyi] Gan (generation of confrontation network) full series (I)
Use the fetch statement to obtain the repetition of the last row of cursor data
IO模型复习
随机推荐
嵌入式背景知识-芯片
【acwing】786. Number k
JMeter loop controller and CSV data file settings are used together
UnityWebRequest基础使用之下载文本、图片、AB包
How to cancel automatic saving of changes in sqlyog database
基于gis三维可视化技术的智慧城市建设
BigDecimal value comparison
Study summary of postgraduate entrance examination in November
Why is the reflection efficiency low?
VS Code指定扩展安装位置
C#记录日志方法
字符串格式化
1321:【例6.3】删数问题(Noip1994)
ISP、IAP、ICP、JTAG、SWD的编程特点
This article explains the complex relationship between MCU, arm, muc, DSP, FPGA and embedded system
单片机(MCU)最强科普(万字总结,值得收藏)
Es classes and objects, prototypes
Postman interface test V
Word自动生成目录的方法
Talking about the return format in the log, encapsulation format handling, exception handling