public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return result;
		ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
		boolean odd = true;
		queue.add(root);
		// add the root to the result
		// result.add(new ArrayList<Integer>(root.val));
		ArrayList<Integer> head = new ArrayList<Integer>();
		head.add(root.val);
		result.add(head);
		while (!queue.isEmpty()) {
			ArrayList<TreeNode> children = getChildren(queue);
			if (children.size() != 0) {
				if (odd) {
					addFromBack(result, children);
					odd = false;
				} else {
					addFromFront(result, children);
					odd = true;
				}
			}
			queue = new ArrayList<TreeNode>();
			queue = children;

		}
		return result;
	}