103. Binary Tree Zigzag Level Order Traversal

 1 //New 用一个记录queue.size(）就可以
 2 class Solution {
 3     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 4         List<List<Integer>> res = new ArrayList<>();
 5         if(root == null) return res;
 6         Queue<TreeNode> queue = new LinkedList<>();
 7         queue.offer(root);
 8         int size = queue.size();
 9         List<Integer> list = new ArrayList<>();
10         boolean seq = false;
11         while(!queue.isEmpty()) {
12             for(int i = 0; i < size; i++) {
13                 TreeNode node = queue.poll();
14                 list.add(node.val);
15                 if(node.left != null) {
16                     queue.offer(node.left);
17                 }
18                 if(node.right != null) {
19                     queue.offer(node.right);
20                 }
21             }
22             if(seq) {
23                 List<Integer> temp = new ArrayList<>();
24                 for(int j = list.size() - 1; j >= 0; j--) {
25                     temp.add(list.get(j));
26                 }
27                 res.add(temp);
28             }else {
29                 res.add(list);
30             }
31             seq = !seq;
32             size = queue.size();
33             list = new ArrayList<>();
34         }
35         return res;
36     }   
37 }
38 
39 
40 
41 //Old HashMap
42 class Solution {
43     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
44         List<List<Integer>> res = new ArrayList<>();
45         if(root == null) return res;
46         Queue<TreeNode> queue = new LinkedList<>();
47         queue.offer(root);
48         HashMap<TreeNode,Integer> map = new HashMap<>();
49         map.put(root,0);
50         int record = 0;
51         List<Integer> list = new ArrayList<>();
52         boolean seq = false;
53         while(!queue.isEmpty()) {
54             TreeNode node = queue.poll();
55             int layer = map.get(node);
56             if(layer != 0 && layer != record) {
57                 if(seq) {
58                     List<Integer> temp = new ArrayList<>();
59                     for(int i = list.size() - 1; i >= 0; i--) {
60                         temp.add(list.get(i));
61                     }
62                     res.add(temp);
63                 }else {
64                     res.add(list);
65                 }
66                 list = new ArrayList<>();
67                 record = layer;
68                 seq = !seq;
69             }
70             list.add(node.val);
71             if(node.left != null) {
72                 queue.offer(node.left);
73                 map.put(node.left,layer+1);
74             }
75             if(node.right != null) {
76                 queue.offer(node.right);
77                 map.put(node.right,layer+1);
78             }
79         }
80         if(seq) {
81             List<Integer> temp = new ArrayList<>();
82             for(int i = list.size() - 1; i >= 0; i--) {
83                 temp.add(list.get(i));
84             }
85             res.add(temp);
86         }else {
87             res.add(list);
88         }
89         return res;
90     }
91     
92 }