Sponsored
Sponsored
This approach leverages the standard Breadth-First Search (BFS) algorithm to perform a level order traversal. We use a queue to traverse the tree level-by-level. For each level, we determine the order (left-to-right or right-to-left) by toggling a flag. At odd levels, we simply reverse the order of elements collected from the queue to achieve the zigzag effect.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(n), for storing the output and additional structures, like the queue used for BFS.
1from collections import deque
2from typing import List, Optional
3
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
12 if not root:
13 return []
14
15 results = []
16 queue = deque([root])
17 left_to_right = True
18
19 while queue:
20 level = deque()
21 for i in range(len(queue)):
22 node = queue.popleft()
23 if left_to_right:
24 level.append(node.val)
25 else:
26 level.appendleft(node.val)
27
28 if node.left:
29 queue.append(node.left)
30 if node.right:
31 queue.append(node.right)
32
33 results.append(list(level))
34 left_to_right = not left_to_right
35
36 return resultsThe Python solution uses deque for both the queue and level list operations to efficiently achieve the zigzag pattern. The toggle mechanism allows levels to be appended left-to-right or right-to-left without compromising on runtime efficiency.
In contrast to the BFS method, this approach utilizes Depth-First Search (DFS) for traversal. Recursive calls are made to process each node, and a hashmap (or similar structure) tracks the current depth. Depending on the depth, nodes are appended to the left or right of the current level list. This achieves the zigzag pattern as the recursion progresses.
Time Complexity: O(n), as DFS visits each node once.
Space Complexity: O(n), considering both storage needs for recursive calls and the result list.
This JavaScript DFS implementation recursively manipulates a result array, inserting at either the start or end of each level array according to current depth parity. Recursive calls facilitate the traversal.