Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
1. 3
2. / \
3. 9 20
4. / \
5. 15 7

return its zigzag level order traversal as:
1. [
2. [3],
3. [20,9],
4. [15,7]
5. ]

Solution:
1. /*
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. * int val;
5. * TreeNode left;
6. * TreeNode right;
7. * TreeNode(int x) { val = x; }
8. * }
9. /
10. public class Solution {
11. public List<List> zigzagLevelOrder(TreeNode root) {
12. List<List> res = new ArrayList<>();
13. 14. if (root == null) {
15. return res;
16. }
17. 18. List list = new ArrayList<>();
19. 20. Stack s1 = new Stack<>();
21. Stack s2 = new Stack<>();
22. 23. boolean leftToRight = true;
24. 25. s1.push(root);
26. 27. while (!s1.isEmpty()) {
28. TreeNode node = s1.pop();
29. 30. list.add(node.val);
31. 32. if (leftToRight) {
33. if (node.left != null) {
34. s2.push(node.left);
35. }
36. 37. if (node.right != null) {
38. s2.push(node.right);
39. }
40. } else {
41. if (node.right != null) {
42. s2.push(node.right);
43. }
44. 45. if (node.left != null) {
46. s2.push(node.left);
47. }
48. }
49. 50. if (s1.isEmpty()) {
51. leftToRight = !leftToRight;
52. res.add(new ArrayList<>(list));
53. list = new ArrayList<>();
54. 55. s1 = s2;
56. s2 = new Stack<>();
57. }
58. }
59. 60. return res;
61. }
62. }