Binary Tree Zigzag Level Order Traversal
Problem Description
Question
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input:root=[3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. BFS using Deque
Intuition:
The zigzag level order traversal requires alternating the direction of each level while we traverse the binary tree. By utilizing a Deque, we can alternate between adding levels to the front or the back, effectively reversing the order of nodes as needed.
Algorithm:
- Initialize a
Dequeto serve as a queue for BFS. - Use a boolean
leftToRightto keep track of the direction of the traversal. - For each level, determine its size, and traverse the nodes. Depending on
leftToRight, we either add nodes to a list normally or reverse them. - Switch the direction for the next level.
- Add the completed levels to the results and return once all levels are processed.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the tree, since we traverse each node once.
- Space Complexity: O(N), needed for the
queuewhich stores nodes at the current level. The largest number of nodes at any level is O(N/2) in a balanced tree.
2. BFS with Two Stacks
Intuition:
Using two stacks allows us to manage two levels of processing: one for the current level and another for the next, enabling us to control the processing order explicitly.
Algorithm:
- Use two stacks: one for current processing (
currentLevel) and another for the next level (nextLevel). - Toggle the direction of node addition to the
nextLevelstack with a booleanleftToRight. - Pop nodes from
currentLevel, and based on the direction, push their children ontonextLevelin appropriate order. - When
currentLevelis empty, swap stacks and repeat until all nodes are processed.
Code:
Complexity Analysis
- Time Complexity: O(N), as every node is processed once from the stacks.
- Space Complexity: O(N), for the space used by the stacks, which at most holds the nodes at one level.