public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		int level = 0;
		Deque<TreeNode> deque = new LinkedList<TreeNode>();
		List<List<Integer>> result = new LinkedList<List<Integer>>();
		if (root == null) {
			return result;
		}
		deque.add(root);
		while (!deque.isEmpty()) {
			Deque<TreeNode> nextLevel = new LinkedList<TreeNode>();
			List<Integer> levelResult = new LinkedList<Integer>();
			Deque<TreeNode> usedToGenerate = new LinkedList<TreeNode>(deque);
			if (level % 2 == 0) {
				// left to right
				while (!deque.isEmpty()) {
					TreeNode cur = deque.removeFirst();
					levelResult.add(cur.val);
				}
			} else {
				// right to left
				while (!deque.isEmpty()) {
					TreeNode cur = deque.removeLast();
					levelResult.add(cur.val);
				}
			}
			while (!usedToGenerate.isEmpty()) {
				TreeNode node = usedToGenerate.removeFirst();
				// always save as queue
				if (node.left != null) {
					nextLevel.addLast(node.left);
				}
				if (node.right != null) {
					nextLevel.addLast(node.right);
				}
			}
			result.add(levelResult);
			deque = nextLevel;
			level++;
		}
		return result;
	}