C#遍历树并查找根到叶子的所有唯一层级链求助

嘿，这个问题其实挺常见的，核心就是用**深度优先搜索（DFS）**来遍历树，同时记录每一条从根到叶子的路径就行。我给你两种实现方式，递归和迭代，你可以根据自己的场景选：

先提前做个小优化 #

首先建议你在Person类的构造函数里初始化Children，避免后续处理空引用异常：

public class Person 
{
    public string Name { get; set; }
    public List<Person> Children { get; set; }

    // 构造函数初始化Children，防止null
    public Person(string name)
    {
        Name = name;
        Children = new List<Person>();
    }
}

方法一：递归实现（简单直观） #

递归的思路很直接：每访问一个节点，就把它加入当前路径；如果这个节点是叶子（没有子节点），就把这条路径存下来；否则继续递归遍历它的所有子节点。

代码示例：

public static List<List<string>> GetAllRootToLeafPaths(Person root)
{
    var result = new List<List<string>>();
    if (root == null) return result;

    // 递归辅助方法
    void Dfs(Person currentNode, List<string> currentPath)
    {
        // 当前节点加入路径
        currentPath.Add(currentNode.Name);

        // 如果是叶子节点，保存路径的副本（必须复制，否则后续修改会影响已保存的路径）
        if (!currentNode.Children.Any())
        {
            result.Add(new List<string>(currentPath));
        }
        else
        {
            // 遍历所有子节点，继续递归
            foreach (var child in currentNode.Children)
            {
                Dfs(child, currentPath);
            }
        }

        // 回溯：从当前路径移除当前节点，处理兄弟节点
        currentPath.RemoveAt(currentPath.Count - 1);
    }

    Dfs(root, new List<string>());
    return result;
}

怎么用？ #

假设你已经构建好了以'A'为根的树：

// 构建示例树
var root = new Person("A");
var b = new Person("B");
var c = new Person("C");
var d = new Person("D");
var e = new Person("E");

root.Children.Add(b);
root.Children.Add(c);
b.Children.Add(d);
c.Children.Add(e);

// 获取所有路径
var paths = GetAllRootToLeafPaths(root);

// 打印结果
foreach (var path in paths)
{
    Console.WriteLine(string.Join(" -> ", path));
}
// 输出：
// A -> B -> D
// A -> C -> E

方法二：迭代实现（避免栈溢出） #

如果你的树特别深，递归可能会触发栈溢出，这时候用迭代的DFS（栈模拟）更安全：

public static List<List<string>> GetAllRootToLeafPathsIterative(Person root)
{
    var result = new List<List<string>>();
    if (root == null) return result;

    // 栈里保存当前节点和对应的路径
    var stack = new Stack<(Person Node, List<string> Path)>();
    stack.Push((root, new List<string> { root.Name }));

    while (stack.Count > 0)
    {
        var (currentNode, currentPath) = stack.Pop();

        // 叶子节点，保存路径
        if (!currentNode.Children.Any())
        {
            result.Add(currentPath);
            continue;
        }

        // 注意这里要倒序入栈，保证遍历顺序和递归一致（可选，看你是否在意顺序）
        foreach (var child in currentNode.Children.Reverse())
        {
            var newPath = new List<string>(currentPath);
            newPath.Add(child.Name);
            stack.Push((child, newPath));
        }
    }

    return result;
}

注意点 #

• 不管递归还是迭代，都要复制路径，不能直接把当前路径的引用加入结果，否则后续修改会覆盖之前的路径。
• 一定要处理Children为null的情况，要么在构造函数初始化，要么在代码里加currentNode.Children?.Any()的判断（不过构造函数初始化更优雅）。

内容的提问来源于stack exchange，提问作者learner