LeetCode 103. Binary Tree Zigzag Level Order Traversal

December 5, 2024

I am glad I was able to make a solution from my own intuition.

Solution

Copy
1from collections import deque
2# Definition for a binary tree node.
3# class TreeNode:
4#     def __init__(self, val=0, left=None, right=None):
5#         self.val = val
6#         self.left = left
7#         self.right = right
8class Solution:
9    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
10        nodes = deque([root] if root else [])
11        rightToLeft = False
12
13        result = []
14        while nodes:
15            level = []
16            children = deque([])
17            for i in range(len(nodes)):
18                if rightToLeft:
19                    node = nodes.pop()
20                    node.right and children.appendleft(node.right)
21                    node.left and children.appendleft(node.left)
22                else:
23                    node = nodes.popleft()
24                    node.left and children.append(node.left)
25                    node.right and children.append(node.right)
26                level.append(node.val)
27            result.append(level)
28            if rightToLeft:
29                nodes += children
30            else:
31                nodes = children + nodes
32            rightToLeft = not rightToLeft
33        return result

Time complexity is O(n) = n and space complexity is O(n).

LeetCode 236. Lowest Common Ancestor of a Binary Tree