递归添加到嵌套结构（四叉树）中的列表

Question

我在 C# 中制作了一个四叉树，当我当前尝试检索四叉树中存储的所有点时。

目前，我的检索函数代码如下所示：

    public List<GameObject> checkMovements(List<GameObject> pts = null)
    {
        if (pts == null)
        {
            pts = new List<GameObject>();
        }
        if (!divided) 
        {
            pts.AddRange(points);
            return pts;
        }

        pts.AddRange(topLeft.checkMovements(pts));
        pts.AddRange(topRight.checkMovements(pts));
        pts.AddRange(bottomLeft.checkMovements(pts));
        pts.AddRange(bottomRight.checkMovements(pts));

        return pts;
    }

topLeft、topRight 等是父四叉树内的嵌套四叉树，所以本质上我的目标是尽可能向下，直到它不再被划分（然后是结束节点），然后添加点存储在那里，然后向上工作。

我认为这是一个关于递归的问题，因为我对它很不熟悉。但我的问题是，当我运行这个时，即使我只添加了 10 个点，它也会返回一个令人难以置信的大列表......大约有数千个点。

我还可以看到，当我调试时，它似乎每次都会增加近一倍。如果需要更多信息，我很乐意提供。

我想不出一种方法来制作一个易于复制的例子，我知道这可能会让一些人犹豫是否要提供帮助。因此，如果您从我的帖子中发现我的代码中有任何突出的错误，我们将不胜感激。谢谢！

Answer 1

看来您的问题可能与您在递归期间处理 pts 列表的方式有关。您应该为四叉树的每个分支创建一个新列表，而不是将相同的列表传递给每个递归调用。这是代码的修改版本：

public List<GameObject>checkMovements(){ 

List<GameObject> pts = new List<GameObject>();

if (!divided) 
{
    pts.AddRange(points);
}
else
{
    pts.AddRange(topLeft.checkMovements());
    pts.AddRange(topRight.checkMovements());
    pts.AddRange(bottomLeft.checkMovements());
    pts.AddRange(bottomRight.checkMovements());
}

return pts;
}

在此修改后的代码中，我从函数签名中删除了 pts 参数，因为我们不需要在递归期间将其传递下去。相反，我们在每次调用 checkMovements() 时创建一个新的 pts 列表。

这应该可以防止列表不受控制地增长，并且应该正确收集存储在四叉树中的点。