Problem overview
The method zigzagTraversal receives the root of a binary tree and returns a List<List<int>>: one inner list per level, with the values of that level. The top level is read from left to right, the next from right to left, the one after that left to right again, and so on.
For the tree [3, 9, 20, null, null, 15, 7], level 0 is [3]. Level 1 holds 9 and 20 from left to right, so it is reported reversed as [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 levels left to right, then flip every second one
Zigzag order is a normal level order traversal with an extra twist on the odd levels. The lesson splits the work into two simple parts instead of trying to produce the zigzag order directly.
- Walk the tree depth first, passing the current level number down. At each node, append its value to the list of its level. Because the left child is always visited before the right child, each level's list fills up from left to right.
- Afterwards, reverse the lists for levels 1, 3, 5 and so on.
Depth first search is not the usual tool for level order, which is normally done with a queue and breadth first search. It works here because the level number is carried along with the recursion, and the order inside one level depends only on visiting left before right. The result is the same as a breadth first approach, with much less code. The other lesson on this problem builds the zigzag order directly with two stacks.
Step by step
- Create the result as a new
List<List<int>>and callDfs(root, 0, result). The root is on level 0. The helper doesn't exist yet, but its job is clear: add every node's value toresult[level]. - Flip the odd levels. Loop with
levelfrom 1 whilelevel < result.Count, stepping by 2, and callReverse()onresult[level]. Level 0 is already in the right order, so the first level to flip is 1. - Return
result. - Declare the helper above the method:
public void Dfs(TreeNode root, int level, List<List<int>> result). Each call handles one node and gives its childrenlevel + 1. - Stop at a missing node. If
root == null, return. This is the base case. - Make sure the level has a list. If
level >= result.Count, add a new emptyList<int>. The search reaches a level for the first time one step at a time, solevelis never more than one past the last list. - Store the value with
result[level].Add(root.val). - Recurse left with
Dfs(root.left, level + 1, result). - Recurse right the same way. Left before right keeps every level in left to right order.
The solution in C#
class Solution {
public void Dfs(TreeNode root, int level, List<List<int>> result) {
if (root == null) {
return;
}
if (level >= result.Count) {
result.Add(new List<int>());
}
result[level].Add(root.val);
Dfs(root.left, level + 1, result);
Dfs(root.right, level + 1, result);
}
public List<List<int>> zigzagTraversal(TreeNode root) {
List<List<int>> result = new List<List<int>>();
Dfs(root, 0, result);
for (int level = 1; level < result.Count; level += 2) {
result[level].Reverse();
}
return result;
}
}
C# details worth knowing:
List<T>.Reverse()works in place. It reverses the list it is called on and returns nothing. That is why the loop calls it as a statement and doesn't assign anything. LINQ also has aReverseextension method that returns a new sequence without changing the original, so assigning or ignoring its result would be a bug. On aList<int>the instance method is the one that is called.- Lists of lists.
List<List<int>>is a list whose elements are lists.result[level].Add(root.val)first indexes the outer list and then adds to the inner one. Indexing pastCountwould throw anArgumentOutOfRangeException, which is the reason for the check that adds the missing level first. - Shared reference.
resultis passed to every recursive call, and all of them add to the same object. - The method name. The lesson's public method is spelled
zigzagTraversal, with a lowercase first letter. Keep that spelling, because the lesson's tests call it by that name.
Complexity
Time: O(n). The search visits each node once. Reversing the odd levels touches each value at most once more, so the whole thing is linear.
Space: O(n) for the output and O(h) for the recursion, where h is the height of the tree. A chain-shaped tree makes h equal to n.
Edge cases and common mistakes
- Empty tree.
Dfsreturns immediately, no level is created and the result is an empty list. - A single node. The result is
[[v]], and the loop never runs becauseresult.Countis 1. - Starting the reverse loop at 0. That would flip the root's level, which is already correct, and shift every flip onto the wrong levels.
- Visiting right before left. Then each level would be built right to left, and flipping the odd levels would reverse the wrong ones.
- Missing nodes inside a level. A level only contains the nodes that exist, so levels can be shorter than a full row. A tree with a missing child still gives correct, shorter lists.
- Forgetting to add the new level's list. Without it, the first node of each new depth would index past the end of
resultand throw.
Testing
[3, 9, 20, null, null, 15, 7]gives[[3], [20, 9], [15, 7]].- A single node
[1]gives[[1]]. - An empty tree gives
[]. - The tree
[1, 2, 3]gives[[1], [3, 2]].