LC 0103 [M] Binary Tree Zigzag Level Order Traversal - ALawliet/algorithms GitHub Wiki
toggle a left-to-right flag for each level
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
Q = deque([root])
ltr = True
while Q:
level = []
for _ in range(len(Q)):
node = Q.popleft()
level.append(node.val)
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
if not ltr: level.reverse()
res.append(level)
ltr = not ltr
return res
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res = []
Q = deque([root])
ltr = True
while Q:
level_size = len(Q)
level = deque()
for _ in range(level_size):
node = Q.popleft()
# if ltr: level.append(node.val) # or
# else: level.appendleft(node.val)
level.append(node.val)
if node.left:
Q.append(node.left)
if node.right:
Q.append(node.right)
level = list(level)
if not ltr: level.reverse() # or
res.append(level)
ltr = not ltr
return res