Let's make `0`

as the root of the tree, the children of the `0`

root can be generated as `1^2,2^2,3^2,...,m^2`

where `m=sqrt(n)`

. Then, the children of the child node `1^2`

can be generated as `1^2+1^2,1^2+2^2,...`

, and the children of `2^2`

can be generated as `2^2+1^2,2^2+2^2,...`

. We apply BFS on the tree to find the first node which equals to the target `n`

. The depth of this node is the least number of perfect square numbers which sum to n.

```
int numSquares(int n) {
int m = sqrt(n);
queue<pair<int,int>> q;
q.push({0, 0});
while (!q.empty())
{
int s = q.front().first;
int depth= q.front().second;
q.pop();
for (int i = 1; i <= m; i++)
{
int a = s + i * i;
if (a < n)
q.push({a, depth + 1});
if (a == n)
return depth + 1;
}
}
return 0;
}
```