Problem overview
The method zigzagTraversal receives the root of a binary tree, a TreeNode | null, and returns its values as an array of arrays, one per level. The levels alternate in direction: the first is read left to right, the second right to left, the third left to right again, and so on.
In the example, the tree built from [3, 9, 20, null, null, 15, 7] looks like this:
3
/ \
9 20
/ \
15 7
Level 0 is [3]. Level 1 holds 9 and 20, which read right to left give [20, 9]. Level 2 holds 15 and 7, read left to right as [15, 7]. The result is [[3], [20, 9], [15, 7]].
Approach: collect left to right, then flip the odd levels
Reading level by level usually suggests a queue. This lesson takes a different route that needs no queue: a depth-first search that carries the current depth. Each node is appended to the list for its level, and because the search always visits the left child before the right child, every level's list fills in left-to-right order, even though the levels are interleaved during the search.
After the search, the zigzag only needs a fix-up: the lists at odd positions (1, 3, 5, and so on) are reversed in place. Separating the two jobs, collecting and then flipping, keeps each one trivial.
The search is recursive. The helper dfs(root, level, result) handles one node: stop if the node is missing, make sure a list exists for this level, append the value, then recurse into the left and right children with level + 1.
Step by step
- Create the result as an empty
number[][]and call the helper on the root with level 0. The root is on level 0. - Flip the odd levels. Loop with
levelstarting at 1 and moving by 2 whilelevel < result.length, and callreverse()on each of those lists. Level 0 stays as it is. - Return the result.
- Write the helper above the method. It takes a node that may be
null, the current level and the shared result array. - Return on a missing node. This base case stops the recursion at the bottom of the tree.
- Add a list for a new level. If
levelis at leastresult.length, push an empty array. The search goes down one level at a time, so a level is never more than one past the last existing list. - Append the node's value to
result[level]. - Recurse left with
level + 1. - Recurse right with
level + 1. Left before right is what keeps every list in left-to-right order.
The solution in TypeScript
class Solution {
dfs(root: TreeNode | null, level: number, result: number[][]): void {
if (!root) {
return;
}
if (level >= result.length) {
result.push([]);
}
result[level].push(root.val);
this.dfs(root.left, level + 1, result);
this.dfs(root.right, level + 1, result);
}
zigzagTraversal(root: TreeNode | null): number[][] {
const result: number[][] = [];
this.dfs(root, 0, result);
for (let level = 1; level < result.length; level += 2) {
result[level].reverse();
}
return result;
}
}
The TypeScript details worth a closer look:
reverse()works in place. It changes the array it is called on and also returns it. The loop ignores the return value because the change toresult[level]is what matters.- Arrays are shared. The helper receives the same
resultarray the caller made, so pushing in any call is visible to all of them. const result. The variable can't be reassigned, but the array can still grow and its inner arrays can still change.- Narrowing. After
if (!root) return;, the compiler knowsrootis aTreeNode, soroot.valandroot.leftare allowed. - Indexing a new level.
result[level].push(...)works only because the line above makes sure that list exists. Reading past the end of an array givesundefined, and callingpushon it would fail.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). The search visits each node once. Reversing the odd levels touches each of their values once more, so the total stays linear.
Space: O(n). The result holds all n values. The recursion adds O(h) of call stack, which is smaller than or equal to the result.
Edge cases and common mistakes
- An empty tree. The helper returns at once, the loop doesn't run and the result is
[]. - A single node. The result is
[[1]]. Level 0 is never reversed. - Starting the flip at level 0. That would reverse the root's level and break every other level's direction. The first level to flip is 1.
- Visiting right before left. Then each list would come out right to left, and flipping the odd levels would give the wrong direction on every level after the root.
- Skipping the new-level check. Without the push of an empty array,
result[level]isundefinedthe first time a level is reached, and.pushthrows. - Single-child nodes. A level can contain nodes whose siblings are missing. Missing children simply don't add values.
Testing
[3, 9, 20, null, null, 15, 7]gives[[3], [20, 9], [15, 7]].[1, 2, 3, 4, 5, 6, 7]gives[[1], [3, 2], [4, 5, 6, 7]].- A single node
[1]gives[[1]]. - An empty tree gives
[].