Leetcode 103: Binary Tree Zigzag Level Order Traversal
grid47 Exploring patterns and algorithms
Oct 27, 2024
7 min read
Solution to LeetCode 103: Binary Tree Zigzag Level Order Traversal Problem
Given the root of a binary tree, your task is to return the zigzag level order traversal of its nodes’ values. This means you need to traverse the tree level by level, alternating between left to right and right to left on each level.
Problem
Approach
Steps
Complexity
Input: You are given the root of a binary tree, where each node has a value and pointers to its left and right children.
Example: root = [4,2,6,1,3,5,7]
Constraints:
• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100
Output: The output should be a 2D array where each element represents a level in the binary tree. For each level, alternate between traversing left to right and right to left.
Example: Output: [[4], [6, 2], [1, 3, 5, 7]]
Constraints:
• The output should be an array of arrays where each inner array contains the values of the nodes at that level, following the zigzag order.
Goal: The goal is to perform a zigzag level order traversal using a breadth-first search (BFS) approach. At every odd level, the node values should be traversed from right to left.
Steps:
• Start by performing a regular level order traversal using a queue.
• After collecting the nodes at each level, reverse the values at odd levels to achieve the zigzag pattern.
• Push the left and right children of each node into the queue to process the next level.
Goal: Ensure the solution can handle a tree with up to 2000 nodes efficiently.
Steps:
• The tree can have between 0 and 2000 nodes.
Assumptions:
• The input is always a valid binary tree.
• Input: root = [3,9,20,null,null,15,7]
• Explanation: The binary tree has the following structure:
3
/ \
9 20
/ \
15 7
The zigzag level order traversal is: [[3], [20, 9], [15, 7]]
• Input: root = [1]
• Explanation: The binary tree consists of just one node, which is the root node. The zigzag level order traversal is: [[1]]
• Input: root = []
• Explanation: An empty tree has no nodes, so the zigzag level order traversal is: []
Approach: The problem can be solved using a breadth-first search (BFS) where nodes are processed level by level. We will alternate the direction of traversal based on the level number.
Observations:
• Zigzag traversal requires alternating the order of nodes on each level.
• By using BFS, we can traverse the tree level by level, and reversing the nodes at odd levels will give us the desired zigzag order.
Steps:
• Perform a regular level order traversal using a queue to process nodes at each level.
• For each level, check if it's an odd or even level. If it’s an odd level, reverse the node values at that level.
• Push the left and right children of each node into the queue for the next level of traversal.
Empty Inputs:
• If the tree is empty (i.e., the root is null), return an empty list.
Large Inputs:
• For large trees with up to 2000 nodes, ensure the solution handles the input efficiently.
Special Values:
• If a node has only one child (either left or right), make sure it is properly handled during the zigzag traversal.
Constraints:
• The tree must be processed within the provided constraints (2000 nodes).
Define the 'zigzagLevelOrder' function which calls 'levelOrder' and modifies the result to achieve zigzag ordering.
19 : Call levelOrder
vector<vector<int>> ans = levelOrder(root);
Call the 'levelOrder' function to get the initial level-order traversal.
20 : Zigzag Traversal
for(int i =1; i < ans.size(); i +=2)
Loop through the result vector and reverse every alternate level to achieve a zigzag order.
21 : Reverse Current Level
vector<int> tmp = ans[i];
Copy the current level into 'tmp' before reversing it.
22 : Reverse Vector
reverse(tmp.begin(), tmp.end());
Reverse the current level to achieve zigzag order.
23 : Assign Reversed Level
ans[i] = tmp;
Assign the reversed level back to the result vector 'ans'.
24 : Return Result
return ans;
Return the final result vector with the zigzag level-order traversal.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In all cases, we must visit each node in the tree once, so the time complexity is O(n), where n is the number of nodes in the tree.
Best Case: O(1)
Worst Case: O(n)
Description: In the worst case, the queue may hold all the nodes at the last level of the tree, resulting in a space complexity of O(n). In the best case, when the tree is perfectly balanced, the space complexity could be reduced to O(log n).
