public ArrayList<Integer> preorderTraversal(TreeNode root) {
		TreeNode[] array = new TreeNode[100];
		ArrayList<Integer> values = new ArrayList<Integer>();
		int depth = 0;
		TreeNode ptr = root;
		TreeNode tmp = null;
		boolean back = false;
		while (ptr != null) {
			if (!back) {
				values.add(ptr.val);
			}
			if (ptr.left != null || ptr.right != null) {
				back = false;
				if (depth >= array.length) {
					array = Arrays.copyOf(array, array.length + 10);
				}
				array[depth++] = ptr;
				if (ptr.left != null) {
					tmp = ptr;
					ptr = ptr.left;
					tmp.left = null;
				} else if (ptr.right != null) {
					tmp = ptr;
					ptr = ptr.right;
					tmp.right = null;
				}
			} else {
				if (depth > 0) {
					ptr = array[--depth];
					back = true;
				} else {
					ptr = null;
				}
			}
		}

		return values;
	}