当前位置:网站首页>LeetCode 103. Binary tree zigzag level order transverse - Binary Tree Series Question 5
LeetCode 103. Binary tree zigzag level order transverse - Binary Tree Series Question 5
2022-07-06 02:16:00 【CP Coding】
Given the root
of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]
. -100 <= Node.val <= 100
The title requires level Z Traverse the whole binary tree in font order , That is, in behavioral units , A line from left to right , The next line is from right to left , In this way, the binary tree is traversed alternately .
If you are familiar with the horizontal traversal binary tree algorithm , This question is relatively simple . I think about it , utilize BFS The algorithm traverses in behavioral units . Define a queue queue, Put the whole row of nodes into the queue each time , In each cycle, all nodes in the current queue ( That is, the nodes of the whole line ) Take out one by one , Put the values into a temporary array , Then take out the left and right child nodes of the node ( If it exists ) Put it in the queue . As required Z Font type , Every other row needs to reverse the temporary array . Finally, add all the numbers of the temporary array to the answer array .
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
l2r = True
q = deque([root])
while q:
n = len(q)
level = []
for i in range(n):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if l2r:
l2r = False
else:
l2r = True
level.reverse()
res.append(level)
return res
边栏推荐
- Extracting key information from TrueType font files
- 【clickhouse】ClickHouse Practice in EOI
- 论文笔记: 图神经网络 GAT
- 【coppeliasim】高效传送带
- Minecraft 1.18.1、1.18.2模组开发 22.狙击枪(Sniper Rifle)
- D22:indeterminate equation (indefinite equation, translation + problem solution)
- How to generate rich text online
- SSM 程序集
- sql表名作为参数传递
- Audio and video engineer YUV and RGB detailed explanation
猜你喜欢
NLP fourth paradigm: overview of prompt [pre train, prompt, predict] [Liu Pengfei]
The intelligent material transmission system of the 6th National Games of the Blue Bridge Cup
Using SA token to solve websocket handshake authentication
[Clickhouse] Clickhouse based massive data interactive OLAP analysis scenario practice
Adapter-a technology of adaptive pre training continuous learning
Tensorflow customize the whole training process
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Exness: Mercedes Benz's profits exceed expectations, and it is predicted that there will be a supply chain shortage in 2022
Audio and video engineer YUV and RGB detailed explanation
How to improve the level of pinduoduo store? Dianyingtong came to tell you
随机推荐
【无标题】数据库中一条查询SQL执行的过程
Ali test Open face test
【coppeliasim】6自由度路径规划
How does redis implement multiple zones?
Jisuanke - t2063_ Missile interception
MySQL learning notes - subquery exercise
Spark accumulator
Redis list
TrueType字体文件提取关键信息
02.Go语言开发环境配置
竞价推广流程
Redis如何实现多可用区?
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Lecture 4 of Data Engineering Series: sample engineering of data centric AI
机器学习训练与参数优化的一般过程 (讨论)
RDD creation method of spark
论文笔记: 图神经网络 GAT
2022 PMP project management examination agile knowledge points (8)
01. Go language introduction
General process of machine learning training and parameter optimization (discussion)