Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-bt
# 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
class Solution:
"""
Thought Process
1 depth=1
/ \
2. 3 depth=2
->[[1],[3,2]]
1
/ \
2 3
/\ /\
4 6 7 8
->[[1],[3,2],[4,6,7,8]]
The below is tricky part:
if depth % 2== 0:
# even
from left to right
else:
# odd
from right to left
"""
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
"""
T:O(n) but it's two passes since each node is only visited once.
S:O(n)
"""
if not root:
return []
zigzag_level_order = []
q = collections.deque([(root, 1)])
while len(q) != 0:
cur_node, depth = q.popleft()
if cur_node.left:
q.append((cur_node.left, depth+1))
if cur_node.right:
q.append((cur_node.right, depth+1))
while len(zigzag_level_order) < depth:
zigzag_level_order.append([])
zigzag_level_order[depth-1].append(cur_node.val)
return [level_order_ls[::-1] if depth%2==1 else level_order_ls for depth, level_order_ls in enumerate(zigzag_level_order)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.