当前位置:网站首页>[牛客网刷题 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
边栏推荐
猜你喜欢
ORM model -- associated fields, abstract model classes
【STM32】STM32烧录程序后SWD无法识别器件的问题解决方法
LeetCode 练习——113. 路径总和 II
LLVM之父Chris Lattner:為什麼我們要重建AI基礎設施軟件
ORM -- database addition, deletion, modification and query operation logic
Review of the losers in the postgraduate entrance examination
The physical meaning of imaginary number J
ORM -- grouping query, aggregation query, query set queryset object properties
Weekly recommended short videos: what are the functions of L2 that we often use in daily life?
Inno setup packaging and signing Guide
随机推荐
Can I open a stock trading account online? Is it safe
The landing practice of ByteDance kitex in SEMA e-commerce scene
Embedded background - chip
Some thoughts on the testing work in the process of R & D
0x0fa23729 (vcruntime140d.dll) (in classes and objects - encapsulation.Exe) exception thrown (resolved)
Postman interface test VII
单片机(MCU)最强科普(万字总结,值得收藏)
Prototype object in ES6
BigDecimal value comparison
Factorial implementation of large integer classes
Review of the losers in the postgraduate entrance examination
2022.7.3DAY595
Chris Lattner, père de llvm: Pourquoi reconstruire le logiciel d'infrastructure ai
@Configuration, use, principle and precautions of transmission:
BigDecimal数值比较
Study summary of postgraduate entrance examination in July
【华为机试真题详解】高矮个子排队
ORM -- logical relation and & or; Sort operation, update record operation, delete record operation
VS Code指定扩展安装位置
Word自动生成目录的方法