public static ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
		// write your code here
		ArrayList<ArrayList<Integer>> rel=new ArrayList<>();
		Queue<TreeNode>q=new ArrayDeque<>();
		if (root!=null)
			q.offer(root);
		boolean even=false;
		while (!q.isEmpty()) {
			ArrayList<Integer>list=new ArrayList<>();
			for (int i=0, n=q.size();i<n;++i) {
				TreeNode t=q.poll();
				list.add(t.val);
				if (t.left!=null)
					q.offer(t.left);
				if (t.right!=null)
					q.offer(t.right);
			}
			if (even)
				Collections.reverse(list);
			even=!even;
			rel.add(list);
		}
		return rel;
	}