Zigzag Level Order of a Binary Tree
Problem statement
Given the root of a binary tree, return its values level by level, alternating direction: the first level (the root) from left to right, the second from right to left, the third from left to right again, and so on.
Return a list with one list of values per level, from the root level down.
Function
zigzagLevels(root: TreeNode) → List<List<Integer>>Examples
Example 1
root = [6,2,8,1,4,7,9]return = [[6],[8,2],[1,4,7,9]]Level 1 is [6]. Level 2 is 2, 8 from left to right, so it is read right to left: [8, 2]. Level 3 goes left to right again: [1, 4, 7, 9].
Example 2
root = [5,3,null,-2,4,null,11]return = [[5],[3],[-2,4],[11]]5 has only a left child, 3, so level 2 is just [3] in either direction. Level 3 holds the children of 3 and is read left to right: [-2, 4]. 11, the right child of -2, is alone on level 4.
Example 3
root = [10,20,30,40,null,null,50,60,70]return = [[10],[30,20],[40,50],[70,60]]Levels from left to right are [10], [20, 30], [40, 50], [60, 70]. Levels 2 and 4 are reversed: [30, 20] and [70, 60].
Constraints
- The tree has between
1and500nodes. -1000 <= node.val <= 1000- The tree does not have to be balanced. It can be a single chain of
500nodes.