public List<List<Integer>> zigzagLevelOrderDeque(TreeNode root) {
		if (root == null) {
			return null;
		}
		
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		
		Deque<TreeNode> deque = new LinkedList<TreeNode>();
		deque.add(null);
		deque.add(root);
		
		while (deque.size() > 1) {
			TreeNode node = deque.poll();
			if (node == null && deque.getFirst() == null) {
				break;
			} else if (node == null) {
				result.add(new ArrayList<Integer>());
				deque.add(null);
				continue;
			}
			
			result.get(result.size() - 1).add(node.val);
			
			if (node.left != null) {
				deque.add(node.left);
			}
			
			if (node.right != null) {
				deque.add(node.right);
			}
		}
		
		return result;
	}