Leetcode: Binary tree zigzag level order traversal
Traverse a tree where the root node is given with a zig-zag level and return the values in a list with one entry per level. For example:
--> 3
/ \
9 5 <--
/ \
--> 7 8
Returns: [[3], [5,9], [7,8]]reverse boolean variable. If the order is reversed, the output values are prepended instead of appended. After each level, the reverse variable is toggled via reverse = not reverse.
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self) -> str:
return f"{self.val}"
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
res = []
queue = [[root]]
reverse = False
while len(queue) > 0:
itms = queue[0]
res.append([])
queue.append([])
for item in itms:
if not item:
continue
if reverse:
# prepend
res[-1] = [item.val] + res[-1]
else:
res[-1].append(item.val)
queue[-1].append(item.left)
queue[-1].append(item.right)
if len(res[-1]) == 0:
queue.pop()
queue = queue[1:]
# Toggle reverse for next level
reverse = not reverse
if len(res[-1]) == 0:
res.pop()
return res
if __name__ == '__main__':
s = Solution().zigzagLevelOrder
print(s(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))), [[3], [20,9], [15,7]])
print(s(TreeNode(1)), [[1]])
print(s(None), [])