LeetCode 솔루션 분류
[2/19] 103. Binary Tree Zigzag Level Order Traversal
본문
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
Accepted
920.5K
관련자료
-
링크
댓글 2
학부유학생님의 댓글
- 익명
- 작성일
import collections
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
dq = collections.deque([])
if root: dq.append(root)
direction = 1
result = []
while dq:
curr_level = []
for i in range(len(dq)):
node = dq.popleft()
curr_level.append(node.val)
if node.left: dq.append(node.left)
if node.right: dq.append(node.right)
result.append(curr_level[::direction])
direction *= -1
return result
JJJJJJJJJJ님의 댓글
- 익명
- 작성일
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
q = collections.deque()
q.append(root)
levelHeight = 0
while q:
qlen = len(q)
val = []
nexLevelStart = qlen
levelHeight = levelHeight + 1
for x in range (qlen):
node = q.popleft()
nexLevelStart -= 1
if node:
val.append(node.val)
if (levelHeight & 0x1 == 0) :
q.insert(nexLevelStart, node.left)
q.insert(nexLevelStart + 1, node.right)
else:
q.insert(nexLevelStart, node.right)
q.insert(nexLevelStart + 1, node.left)
if len(val):
res.append(val)
return res
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
q = collections.deque()
q.append(root)
levelHeight = 0
while q:
qlen = len(q)
val = []
nexLevelStart = qlen
levelHeight = levelHeight + 1
for x in range (qlen):
node = q.popleft()
nexLevelStart -= 1
if node:
val.append(node.val)
if (levelHeight & 0x1 == 0) :
q.insert(nexLevelStart, node.left)
q.insert(nexLevelStart + 1, node.right)
else:
q.insert(nexLevelStart, node.right)
q.insert(nexLevelStart + 1, node.left)
if len(val):
res.append(val)
return res
