递归获取ID

Question

哈啰！

我有一个 List 其中 Channel 是一个自定义类 offcourse:

public class Channel 
{
    public long ID { get; set; }
    public long parentID { get; set; }
}

strcuture 可以是这样的：

ID = 1, parentID = 0
    ID = 64, parentID = 1
        ID = 28, parentID = 64
        ID = 36, parentID = 64
ID = 5, parentID = 0

等等。

我想做的是获取特定频道的所有儿童 ID：

function List<long> getChildrenIDS (long ID)
{
    // WHAT GOES HERE?
}

Answer 1

要获取所有子项：

public IEnumerable<long> GetChildren(List<Channel> list, long id)
{
  foreach(Channel c in list)
    if(c.parentID == id)
      yield return c.ID;
}

将其构建为返回 IEnumerable，而不是返回 List，然后调用需要 List的代码。 可以使用 new List(GetChildren(list, id)) 或 GetChildren(list, id).ToList()，而调用不需要此功能的代码时，可以通过不构建实际上不需要的列表来获得更好的内存性能和获得第一个结果的时间，如 foreach( GetChildren(list, id)) 中的长 childID。

要获得所有后代（孩子、孙子、曾孙等），这是我们可以使用递归（根据您的问题标题）的唯一情况，请使用：

假设不能重复（通过多个路由的同一个孙子）：

private IEnumerable<long> GetDescendants(List<Channel> list, long id)
{
   foreach(long child in GetChildren(list, id))
   {
     yield return child;
     foreach(long grandchild in GetDescendants(list, child))
       yield return grandchild;
   }
}

如果可能有重复，那么您可以将 .Distinct() 应用于上面，或者选择：

private IEnumerable<long> GetDescHelper(List<Channel> list, long id, HashSet<long> already)
{
  foreach(long child in GetChildren(list, id))
    if(already.Add(child))
    {
      yield return child;
      foreach(long desc in GetDescHelper(list, child, already))
        yield return desc;
    }
}
public IEnumerable<long> GetDescendants(List<Channel> list, long id)
{
  return GetDescHelper(list, id, new HashSet<long>());
}

这就是说，我可能宁愿通过让 Channel 类维护一个来对此进行建模子项List。

Answer 2

不知道 Marcos 的答案是否真的产生了所需的结果，但我会以更 LINQish 的方式编写：

private IEnumerable<long> GetChildrenIds(IEnumerable<Channel> channels, long parentId)
{
    if(channels == null)
        throw new ArgumentNullException("channels");

    var childs = channels.Where(c => c.ParentId == parentId)
                         .Select(c => c.Id);

    return childs;
}

如果您还需要深层嵌套的，您可能可以使用此函数：

private IEnumerable<long> GetAllChildrenIds(IEnumerable<Channel> channels, long parentId)
{
    var childs = GetChildrenIds(channels, parentId);
    var alldescendants = childs.SelectMany(id => GetAllChildrenIds(channels, id));

    return childs.Concat(alldescendants);
}

但请注意，它不会检查循环冗余并可能最终导致 stackoverflow 异常！

Answer 3

在

List<Channel> list = new List<Channel>();
List<long> ret = new List<long>();

你的班级中，你可以这样做：

没有递归（所以只有孩子）

private List<long> GetChildrenIds(long parentId)
{
    list.ForEach(p => { if (p.parentID == parentId) ret.Add(p.ID); });
    return ret;
}

或有递归（孩子的孩子也是如此）

private List<long> GetChildrenIds(long parentId)
{
    list.ForEach(p => { if (p.parentID == parentId) { 
                            ret.Add(p.ID); 
                            GetChildrenIds(p.ID); 
                        } 
                      });
    return ret;
}