$\textbf{Answer:} (x+c)^n, c\in\mathbb{Z}, n\in\mathbb{Z}^+_0$

$\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ Let $n=deg P$ If $P$ is constant obviously $P\equiv 1$or $P\equiv 0$, so let's assume $n\geq 1$ By the condition for all $a\in \mathbb{Z} , \exists x_a\in\mathbb{Z} / P(x_a)=P(a)^n$ We also know that $P(a)^n$ takes infinite values $\Rightarrow P(x)$, $x\in\mathbb{Z}$ takes infinite $n-$th power values $...(I)$ Let $\alpha\in\mathbb{R}/P(x)-(x+\alpha)^n$ be a polynomial of degree $n-2$ at most If $\alpha\not \in\mathbb{Z}:$ $\Rightarrow (x+\lfloor \alpha \rfloor)^n<P(x)<(x+\lceil \alpha \rceil)^n,\forall x\in\mathbb{Z}$ big enough. By $(I) (\Rightarrow \Leftarrow)$ If $\alpha \in\mathbb{Z}:$ $\Rightarrow (x+\alpha-1)^n<P(x)<(x+\alpha+1)^n,\forall x\in\mathbb{Z}$ big enough $\Rightarrow P(x)=(x+\alpha)^n$ for infinite $x$ $$\Rightarrow P(x)\equiv (x+\alpha)^n_\blacksquare$$$\color{blue}\rule{24cm}{0.3pt}$