[leetcode] 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],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

分析：题目要求之字形层次遍历一个二叉树。

思路一：层次遍历肯定想到用BFS，习惯于用队列queue实现，这个问题实现思路也比较简单，维持一个boolean类型变量表示：0代表从右到左，1代表从左到右就可以了。

就不贴上代码了。

思路二：既然可以用队列，肯定也可以用栈做。维持两个栈实现功能，代码如下：

 1 class Solution {
 2     List<List<Integer>> res = new ArrayList<>();
 3     Stack<TreeNode> l_r = new Stack<>();
 4     Stack<TreeNode> r_l = new Stack<>();
 5     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 6         if ( root == null ) return res;
 7         l_r.push(root);
 8         List<Integer> a = new ArrayList<>();
 9         a.add(root.val);
10         res.add(a);
11         while ( !l_r.isEmpty() || !r_l.isEmpty() ){
12             if ( !l_r.isEmpty() ){
13                 int size = l_r.size();
14                 List<Integer> list = new ArrayList<>();
15                 for ( int i = 0 ; i < size ;i ++ ){
16                     TreeNode t = l_r.pop();
17                     if ( t.right != null ) {
18                         list.add(t.right.val);
19                         r_l.push(t.right);
20                     }
21                     if ( t.left != null ) {
22                         list.add(t.left.val);
23                         r_l.push(t.left);
24                     }
25                 }
26                 if ( !list.isEmpty() ) res.add(list);
27             }
28             if ( !r_l.isEmpty()){
29                 int size = r_l.size();
30                 List<Integer> list = new ArrayList<>();
31                 for ( int i = 0 ; i < size ;i ++ ){
32                     TreeNode t = r_l.pop();
33                     if ( t.left != null ) {
34                         list.add(t.left.val);
35                         l_r.push(t.left);
36                     }
37                     if ( t.right != null ) {
38                         list.add(t.right.val);
39                         l_r.push(t.right);
40                     }
41 
42                 }
43                 if ( !list.isEmpty() ) res.add(list);
44             }
45         }
46         return res;
47     }
48 }

AC 2ms，看了一下1ms的答案，都是用queue做的，因为比较熟了。就不写queue的代码了。