题目：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路：

用两个栈存储奇数层和偶数层即可。

源码：GitHub源码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        int layer = 1;
        stack1.push(root);
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(layer % 2 == 1){
                 while(!stack1.isEmpty()){
                     if(stack1.peek().left != null) stack2.push(stack1.peek().left);
                     if(stack1.peek().right != null) stack2.push(stack1.peek().right);
                     list1.add(stack1.pop().val);
                 }
            }else{
                while(!stack2.isEmpty()){
                    if(stack2.peek().right != null) stack1.push(stack2.peek().right);
                    if(stack2.peek().left != null) stack1.push(stack2.peek().left);
                    list1.add(stack2.pop().val);
                }
            }
            if(!list1.isEmpty()){
                list.add(new ArrayList(list1));
                list1.clear();
                layer++;
            }
        }
        return list;
    }
}

注意：

下面代码错误原因：

• ll = null;并不是将ll置空，而是可以理解为没有对list集合分配内存空间，实际上压根就不存在。所以此时将ll的声明拿到上面去肯定是错的。
• 当采用ll使用后置空的方法时，在将ll添加到list中时，需要list.add(new ArrayList(ll)); 因为add添加的是引用，如果不new一个的话，后面的操作会更改这个list，导致结果为null。

/** Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * } */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer>ll = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack1 = new Stack<>();//存储奇数层
        Stack<TreeNode> stack2 = new Stack<>();//存储偶数层
        int layer  = 1;//奇数表示奇数层，偶数表示偶数层
        stack1.push(root);
        while(!stack1.empty() || !stack2.empty()){
            if(layer % 2 == 1){
                while(!stack1.empty()){
                    if(stack1.peek().left != null) stack2.push(stack1.peek().left);
                    if(stack1.peek().right != null) stack2.push(stack1.peek().right);
                    ll.add(stack1.pop().val);
                }
                if(!ll.isEmpty()){
                    list.add(ll);
                    ll = null;
                    layer++;
                }
            }else{
                while(!stack2.empty()){
                    if(stack2.peek().right != null) stack1.push(stack2.peek().right);
                    if(stack2.peek().left != null) stack1.push(stack2.peek().left);
                    ll.add(stack2.pop().val);
                }
                if(!ll.isEmpty()){
                    list.add(ll);
                    ll = null;
                    layer++;
                }
            }
        }
        return list;
    }
}

正确应为：

/** Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * } */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer>ll = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack1 = new Stack<>();//存储奇数层
        Stack<TreeNode> stack2 = new Stack<>();//存储偶数层
        int layer  = 1;//奇数表示奇数层，偶数表示偶数层
        stack1.push(root);
        while(!stack1.empty() || !stack2.empty()){
            if(layer % 2 == 1){
                while(!stack1.empty()){
                    if(stack1.peek().left != null) stack2.push(stack1.peek().left);
                    if(stack1.peek().right != null) stack2.push(stack1.peek().right);
                    ll.add(stack1.pop().val);
                }
                if(!ll.isEmpty()){
                    list.add(new ArrayList(ll));
                    ll.clear();
                    layer++;
                }
            }else{
                while(!stack2.empty()){
                    if(stack2.peek().right != null) stack1.push(stack2.peek().right);
                    if(stack2.peek().left != null) stack1.push(stack2.peek().left);
                    ll.add(stack2.pop().val);
                }
                if(!ll.isEmpty()){
                    list.add(new ArrayList(ll));
                    ll.clear();
                    layer++;
                }
            }
        }
        return list;
    }
}