又开始刷算法题了，正好在学Java，顺便也练练Java。

题目描述

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

我的解答：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
import java.util.Queue;

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
        ArrayList<Integer> tem=new ArrayList<>();
        TreeNode lastNode=root;
        TreeNode levelNode=root;
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        int cnt=0;
        while(q.size()!=0){
            TreeNode poll=q.poll();
            tem.add((Integer)poll.val);
            if(poll.left!=null){
                q.offer(poll.left);
                lastNode=poll.left;
            }
            if(poll.right!=null){
                q.offer(poll.right);
                lastNode=poll.right;
            }
            if(levelNode==poll){
                if(cnt%2!=0){
                    Collections.reverse(tem);
                }
                levelNode=lastNode;
                ans.add(new ArrayList<>(tem));
                tem.clear();
                cnt++;
            }
        }
        return ans;
    }
}

遇到的坑&&小结：

• 把Collections当成了Collection。实际上，Collections是一个包装类，可以当成专门为Collection中的类服务的工具类，不能被实例化；而Collection是根接口
• Java引用变量有两个类型:一个是编译时的类型，一个是运行时的类型。编译时由声明该变量时使用的类型决定，运行时由实际赋值给它的对象的类型决定，当编译时的类型和运行时的类型不一样时，就产生了所谓的多态
• 在多态中，引用类型时接口或父类，而正真的实现类型是实现接口的类的对象或继承父类的子类对象。比如：Queue<TreeNode> q=new LinkedList<>();其中，引用类型是Queue这个接口，实现类型（也就是运行时的类型）是LinkedList这个实现了Queue接口的类
• 多态性是对象多种表现形式的体现
• `ArrayList> res = new ArrayList>();
  一般都不这么写（我一开始不造），一般都写成ArrayList> res = new ArrayList<>();`因为不写默认跟前面的走，这是泛型规定的