Problem overview
The method zigzagTraversal receives the root of a binary tree and returns its values level by level as an Array[Array[Int]]. The first level is read from left to right, the next from right to left, and the direction keeps alternating.
For the tree with root 3, left child 9 and right child 20, where 20 has the children 15 and 7, the answer is [[3], [20, 9], [15, 7]]. Level 0 is [3]. Level 1 holds 9 and 20 from left to right, so it is reversed into [20, 9]. Level 2 holds 15 and 7 and is read from left to right again.
Approach: collect the levels, then flip every second one
Two things are needed: the values grouped by level, and a reversal of every other group. A common way to group by level is a breadth-first search with a queue. This lesson uses a depth-first search instead, which is shorter in Scala.
A depth-first search that passes the current level down knows each node's level. When it reaches a node on level level, it appends the node's value to the list for that level. The list is created the first time the search reaches that level. If the search always visits the left child before the right child, then each level's list is in left-to-right order, because on any level the nodes are reached from left to right.
After the search, every odd level (1, 3, 5, and so on) is reversed. Level 0 is the root and stays as it is. Finally, the buffers are converted to arrays, since the method returns arrays.
Step by step
- Create
resultas an emptyArrayBuffer[ArrayBuffer[Int]]with the full package name, then calldfs(root, 0, result). The root is on level 0. A buffer can grow level by level, which a plainArraycan't. - Reverse the odd levels with
for (level <- 1 until result.length by 2). The range starts at 1 and steps by 2. Inside, assignresult(level).reverseback toresult(level):reversereturns a new buffer and leaves the original unchanged. - Convert the result.
result.map(_.toArray)turns each inner buffer into an array, and the outertoArrayturns the outer buffer into an array. It is the last expression. - Declare the helper
dfswith the parametersroot: TreeNode,level: Intandresult. It returnsUnit. - Stop on
null. A missing child ends the recursion by returning at once. - Make sure the level has a list. If
level >= result.length, append a new emptyArrayBuffer[Int](). The search goes down one level at a time, solevelis never more than one past the last list. - Add the value with
result(level) += root.value. - Recurse left with
dfs(root.left, level + 1, result). - Recurse right the same way. Left before right keeps each level in left-to-right order.
The solution in Scala
class Solution {
def dfs(root: TreeNode, level: Int, result: scala.collection.mutable.ArrayBuffer[scala.collection.mutable.ArrayBuffer[Int]]): Unit = {
if (root == null) {
return
}
if (level >= result.length) {
result += scala.collection.mutable.ArrayBuffer[Int]()
}
result(level) += root.value
dfs(root.left, level + 1, result)
dfs(root.right, level + 1, result)
}
def zigzagTraversal(root: TreeNode): Array[Array[Int]] = {
val result = scala.collection.mutable.ArrayBuffer[scala.collection.mutable.ArrayBuffer[Int]]()
dfs(root, 0, result)
for (level <- 1 until result.length by 2) {
result(level) = result(level).reverse
}
result.map(_.toArray).toArray
}
}
Scala details:
1 until result.length by 2is a range that starts at 1, excludesresult.lengthand steps by 2. If there is only one level, the range is empty and the loop body never runs. For 6 levels it is 1, 3, 5.result(level) += root.valueappends to the inner buffer found at that position. Because the inner buffers are mutable objects, the change is visible throughresult.result(level) = ...replaces the element in the outer buffer. This is needed becausereversedoesn't change the buffer it is called on._.toArrayis shorthand forx => x.toArray. The outertoArraythen needs the element typeArray[Int], which the compiler infers from the declared return type.- Printing. Printing an
Arrayshows a reference, not its contents. UsemkStringto see the values.
Complexity
Time: O(n). The search visits each node once. The reversals touch each value on an odd level once more, and the conversions copy each value once, so the total stays linear.
Space: O(n) for the result, plus O(h) for the recursion, where h is the height of the tree, the depth of the deepest node.
Edge cases and common mistakes
- Empty tree. With
root = nullthe search adds nothing and the method returns an empty array. - A single node returns
[[value]]. The range for the reversal loop is empty. - A chain. Four nodes, each the left child of the previous one, give four levels of one value each:
[[1], [2], [3], [4]]. Reversing a one-element level changes nothing. - Full tree. The tree with root 1, children 2 and 3, and leaves 4, 5, 6, 7 gives
[[1], [3, 2], [4, 5, 6, 7]]. Level 1 is flipped and level 2 is not. - Reversing even levels, starting the loop at 0 instead of 1, flips the root's level and every even one, which gives the opposite pattern.
- Not assigning the reversed buffer back. Calling
result(level).reversealone computes a new buffer and throws it away. - Visiting the right child first. That would make every level come out right to left and the later reversal would then flip the wrong levels.
Testing
- Root 3 with children 9 and 20, and 20 with children 15 and 7:
[[3], [20, 9], [15, 7]]. - Root 1 with children 2 and 3, and leaves 4, 5, 6, 7:
[[1], [3, 2], [4, 5, 6, 7]]. null: an empty array.
