Solution:

We quickly check that $P \equiv 0$ is indeed a solution. So from here on out let's assume $P \not \equiv 0$. Plugging in $x=n$, we get that $P(n)=0$, from which it follows that $P(x)=(x-n)^{r} Q(x)$, for some polynomial $Q \in \mathbb{R}[x]$ with $Q(n) \neq 0$. We now have
$$\left(x^{2}+x-n-n^{2}\right)^{r} Q\left(x^{2}+x-n^{2}\right)=(x-n)^{2 r} Q(x)+(x-n)^{r} Q(x)$$
Factoring out and dividing by $(x-n)^{r}$, we get
$$(x+n+1)^{r} Q\left(x^{2}+x-n^{2}\right)=(x-n)^{r} Q(x)+Q(x)$$
But if we plug in $x=n$, we get $0=Q(n)$, a contradiction. So $P \equiv 0$ is the only solution.

Solution:

Plugging in $x=-n$ yields $P(-n)=0$. Next, $x=n-1$ gives us $0=P(-n)=P(n-1)^{2}+P(n-1)$ and so $P(n-1) \in\{-1,0\}$. Note that the quadratic equation $x^{2}+x-n^{2}=n-1$ certainly has a positive solution $x_{1}$, namely
$$x_{1}=\frac{-1+\sqrt{1+4\left(n^{2}+n-1\right)}}{2}=\frac{\sqrt{4 n^{2}+4(n-1)+1}-1}{2}$$
We also observe that $n-1<x_{1}<n$. If $P(n-1)=-1$, plugging $x=x_{1}$ into the original equation would yield $-1=P(n-1)=P\left(x_{1}\right)^{2}+P\left(x_{1}\right)$. However, $y^{2}+y \geq-1 / 4$ for all $y \in \mathbb{R}$, contradiction! We conclude that $P(n-1)=0$ and the equation becomes $0=P\left(x_{1}\right)^{2}+P\left(x_{1}\right)$. Similarly to above, $P\left(x_{1}\right) \in\{-1,0\}$. This is basically the situation that we faced at the beginning, except that we replaced $n-1$ by $x_{1}$. Hence we try to iterate the argument:
Again, the equation $x^{2}+x-n^{2}=x_{1}$ certainly has a solution, since $x_{1}>0$. Let
$$x_{2}=\frac{\sqrt{4 n^{2}+4 x_{1}+1}-1}{2}$$
be the positive solution. Since $x_{1}<n$, we easily get $x_{2}<n$ as well. Furthermore,
$$4 x_{2}^{2}+4 x_{2}+1=\left(2 x_{2}+1\right)^{2}=4 n^{2}+4 x_{1}+1 \Rightarrow x_{2}>x_{1}$$
since if $x_{1} \geq x_{2}$, the right hand side would be strictly larger than the left hand side (as $x_{2}<n$ ). Plugging $x=x_{2}$ into the original equation yields $P\left(x_{1}\right)=P\left(x_{2}\right)^{2}+P\left(x_{2}\right)$. By the same reasoning as above, we conclude that $P\left(x_{1}\right)=-1$ is impossible and hence $P\left(x_{1}\right)=0$ and $P\left(x_{2}\right) \in\{-1,0\}$. It is easy to see that we can iterate this argument by replacing $x_{1}$ by $x_{k}$ and $x_{2}$ by $x_{k+1}$ in the $k$-th step. We obtain an arbitrarily long sequence $n-1<x_{1}<x_{2}<\ldots<n$ of distinct zeros of $P$. Since any non-zero polynomial only has a finite number of roots, we conclude that $P$ must be the constant zero-polynomial. This is indeed a solution.

Solution:

Let $f(x)=x^{2}+x-n^{2}$ and $g(x)=x^{2}+x$. The equation can then be rewritten as
$$P(f(x))=g(P(x))$$
Now note that $f(\mathbb{R})=\left[-n^{2}-\frac{1}{4}, \infty\right)$ and $g(\mathbb{R})=\left[-\frac{1}{4}, \infty\right)$. So from this we get
$$P(y) \geq-\frac{1}{4}, \text{ for } y \in\left[-n^{2}-\frac{1}{4}, \infty\right)$$
So if $x \geq-n^{2}-\frac{1}{2}$ and $f(x)$ is a root of $P$, we have that $0=g(P(x))$, so $P(x)=-1$ or $P(x)=0$. But because $P(x) \geq-\frac{1}{2}, P(x)$ can't be -1 and $x$ is a root of $P$.
First we solve the case $n=1$ and then we solve the case $n \geq 2$. Plugging in $n=-1$, we get that $P(-1)=0$. Now since $f(0)=-1$, it follows from the argument above, that $P(0)=0$. Similarly, since $f\left(\frac{1+\sqrt{(5)}}{2}\right)=0, \frac{1+\sqrt{(5)}}{2}$ is also a root of $P$. Now note that $f(x)>x$, for $x>1$. such that $a_{2 i} \in\left[-\frac{1}{2}, n\right)$ and $a_{2 i-1} \in\left[-n-1,-\frac{1}{2}\right]$
Now by plugging in $x=-n$, we find that $P(-n)=0$. We will now inductively construct a series $\left(a_{i}\right)_{i \in \mathbb{N}}$ consisting of pairwise distinct roots of $P$, such that $a_{i} \geq-n^{2}-\frac{1}{4}$. If we succeed to construct such a series, it'll follow immediately, that $P \equiv 0$ is indeed the only solution.
To do that define
$$\begin{aligned} f_{-}: & \left(-\infty,-\frac{1}{2}\right] \rightarrow\left[-n^{2}-\frac{1}{4}, \infty\right) & f_{+}:\left[-\frac{1}{2}, \infty\right) & \rightarrow\left[-n^{2}-\frac{1}{4}, \infty\right) \\ x & \mapsto f(x) & x & \mapsto f(x) \end{aligned}$$
So in other words $f_{-}$ and $f_{+}$ are the restrictions of $f$ to $\left(-\infty,-\frac{1}{2}\right]$ and $\left[-\frac{1}{2}, \infty\right)$ respectively. Note that $f_{-} / f_{+}$ are strictly decreasing/increasing and thereby bijective.
First we solve the case $n=1$ and then we solve the case $n \geq 2$. Plugging in $n=1$, we get that $P(1)=0$. Now since $0=f_{+}^{-1}(1)$, it follows from the argument above, that $P(0)=0$. Similarly, since $\frac{1+\sqrt{(5)}}{2}=f_{+}^{-1}(0), \frac{1+\sqrt{(5)}}{2}$ is also a root of $P$. Now note that $f(x)>x$, for $x>1$. Define $a_{1}:=\frac{1+\sqrt{(5)}}{2}$ and then $a_{k+1}=f_{+}^{-1}\left(a_{k}\right), \forall k \geq 2$. It is easy to check, that all the $a_{k}$ are well defined and distinct roots of $P$, finishing the case $n=1$.
Ok, now to the the case $n \geq 2$. Here we set a further constraint on the series $\left(a_{i}\right)_{i \in \mathbb{N}}$. Namely $a_{2 i} \in\left[-n-1,-\frac{1}{2}\right]$ and $a_{2 i-1} \in\left[-\frac{1}{2}, n\right]$ for all $i \in \mathbb{N}$.
Set $a_{1}:=n$, which is indeed a root of $P$ and in the interval $\left[-\frac{1}{2}, n\right]$.
Now assume we already have $a_{1}, \ldots, a_{k}$. If $k$ is odd define $a_{k+1}:=f_{+}^{-1}\left(a_{k}\right)$, else set $a_{k+1}:=f_{-}^{-1}\left(a_{k}\right)$. So let's check that $a_{k+1}$ is well defined, lies in $\left[-n-1,-\frac{1}{2}\right]$ for $k$ even, lies in $\left[-\frac{1}{2}, n\right]$ for $k$ odd and is a root of $P$.
$k$ even:
- $a_{k+1}$ is well defined, as $f_{-}$ is bijective and $a_{k} \in\left[-\frac{1}{2}, n\right] \subset\left[-n^{2}-\frac{1}{4}, \infty\right)$.
- Using the strict monotony of $f_{-}$, one can find that $f_{-}^{-1}\left(\left[-\frac{1}{2}, n\right]\right)=\left[-n-1, \frac{-1-\sqrt{4 n^{2}-1}}{2}\right] \subset \left[-n-1,-\frac{1}{2}\right]$. So by construction of $a_{k+1}$, it lies in the interval $\left[-n-1,-\frac{1}{2}\right]$
- We have that $g\left(P\left(a_{k+1}\right)\right)=P\left(f\left(a_{k+1}\right)\right)=P\left(a_{k}\right)=0$. So $P\left(a_{k+1}\right)$ is a root of $g(x)$ and thereby equal to -1 or 0. But now $a_{k+1} \in\left[-n-1,-\frac{1}{2}\right] \subset\left[-n^{2}-\frac{1}{4}, \infty\right)$, as $n \geq 2$, forcing $P\left(a_{k+1}\right)=0$.
$k$ odd:
- $a_{k+1}$ is well defined, as $f_{+}$ is bijective and $a_{k} \in\left[-n-1,-\frac{1}{2}\right] \subset\left[-n^{2}-\frac{1}{4}, \infty\right)$, as $n \geq 2$.
- Using the strict monotony of $f_{+}$, one can find that $f_{+}^{-1}\left(\left[-n-1,-\frac{1}{2}\right]\right)=\left[\frac{-1+\sqrt{4 n^{2}-4 n-3}}{2}, \frac{-1+\sqrt{4 n^{2}-1}}{2}\right] \subset \left[-\frac{1}{2}, n\right]$. So by construction of $a_{k+1}$, it lies in the interval $\left[-\frac{1}{2}, n\right]$
- We have that $g\left(P\left(a_{k+1}\right)\right)=P\left(f\left(a_{k+1}\right)\right)=P\left(a_{k}\right)=0$. So $P\left(a_{k+1}\right)$ is a root of $g(x)$ and thereby equal to -1 or 0. But now $a_{k+1} \in\left[-\frac{1}{2}, n\right] \subset\left[-n^{2}-\frac{1}{4}, \infty\right)$, forcing $P\left(a_{k+1}\right)=0$.